HackerRank 문제풀이 - 3 (Repeated String)

1. 문제

 

• 하나의 문자열(s)이 주어지고, 길이(n)가 주어질 때, 해당 문자열을 해당 길이까지 동안 반복하였을때, "a" 개수를 찾는 문제이다. 
  • 최대 길이는 1부터 10^12까지 주어질 수 있어, 계산 성능의 최적화가 필요하다.

 

---

2. 1차 풀이 

2.1 풀이 과정

'use strict';

import { WriteStream, createWriteStream } from "fs";
process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString: string = '';
let inputLines: string[] = [];
let currentLine: number = 0;

process.stdin.on('data', function(inputStdin: string): void {
    inputString += inputStdin;
});

process.stdin.on('end', function(): void {
    inputLines = inputString.split('\n');
    inputString = '';

    main();
});

function readLine(): string {
    return inputLines[currentLine++];
}

/*
 * Complete the 'repeatedString' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts following parameters:
 *  1. STRING s
 *  2. LONG_INTEGER n
 */
function repeatedString(s: string, n: number): number {
    // Write your code here
    
    const maxStrLength = s.length
    let amountOfA = 0;
    let sPos = 0;
    
    for(let i = 0; i < n; i++){
        if(s.charAt(sPos) === "a") amountOfA += 1;
        
        sPos +=1
        if(sPos == maxStrLength) sPos = 0
    }
    
    return amountOfA
}

function main() {
    const ws: WriteStream = createWriteStream(process.env['OUTPUT_PATH']);
    const s: string = readLine();
    const n: number = parseInt(readLine().trim(), 10);
    const result: number = repeatedString(s, n);
    ws.write(result + '\n');
    ws.end();
}

계산 방법은 다음과 같다.

• 주어진 문자열(s)의 길이를 구한다.
• 0부터 주어진 반복길이(n)까지 반복문을 돈다.
  •  "a" 문자를 발견하면, 갯수를 카운팅한다.
  • 탐색하는 문자열의 위치를 1 증가시킨다.
  • 만일 주어진 문자열(s)의 길이보다 문자열 위치가 높아진다면, 문자열 위치를 0으로 초기화시킨다.

 

2.2 풀이 결과

그렇다. 너무 쉽게 풀어가려고 했다. example로 적은수의 최대 길이값이 이 주어졌을 때에는 통과하였지만, 많은수의 최대 길이값이 주어졌을 때에는, 제한된 시간 내에 계산되지 못하여서 통과하지 못하였다.

 

 

당연하게도, 문자열을 하나씩 검사하면서 1조번 iteration을 돌려고 하니 성능이 흉측할 수밖에..

 

3. 2차 풀이

3.1 풀이 과정

그래서, 풀이 과정을 수정하여 아래와 같이 작성하게 되었다.

 

(작성하는 주요 함수만 아래에 첨부했다.)

function repeatedString(s: string, n: number): number {
    // Write your code here
    
    const strLength = s.length
    
    const quotiant = Math.floor(n/strLength);
    const remainder = n % strLength;
    
    
    let countOfaInStr = 0;
    let countOfaInStrWithInRemainder = 0;
    s.split("").forEach((c, index)=> {
        if(c === "a") {
            countOfaInStr++
            
            if(index < remainder) {
                countOfaInStrWithInRemainder ++
            }
        }
    })
    
    return (countOfaInStr * quotiant) + countOfaInStrWithInRemainder
}

 

2차 풀이 과정은 다음과 같다.

• 주어진 문자열(s)의 길이를 구한다.
• 주어진 최대길이(n)에 주어진 문자열의 길이를 나누어 몫과 나머지를 구한다.
• 주어진 문자열(s)에 반복문을 돌면서 아래의 값을 계산한다.
  • 문자열에 "a" 가 포함된 갯수를 구한다.
  • 위에서 구한 나머지 값보다 작은 문자열 길이 내에 "a"가 포함된 갯수를 구한다.
• 위에서 구한 몫과 "a"가 포함된 갯수를 곱하고, 나머지 값보다 적은 길이 내에 포함되었언 "a" 갯수를 더하여 최종 결과로 반환한다.

 

2차로 풀이한 방식은 주어진 최대길이(n)만큼 주먹구구식으로 반복문을 도는것이 아닌, 수학적으로 계산하여 값을 추출하는 방식이다. 아래의 결과를 보자.

 

 

3.2 풀이 결과

아까 통과하지 못했던 n = 1000000000000 으로 주어졌을때의 Test case를 포함한 나머지 Test case들도 통과함을 확인할 수 있다.