Repeated String

 

https://www.hackerrank.com/challenges/repeated-string/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup 

Repeated String | HackerRank

 

문제 이해 및 분석

  1. 주어진 s 에 'a' 가 몇개 있는지 알아야 한다.

  2. 주어지는 s는 최대 n 의 길이에 도달할때 까지 반복된다.

 

문제 풀이

 1. o(1) 로 풀어야 한다.

 2. 먼저 주어진 s에 'a'가 몇번 반복되는지 구한다.

 3. 그리고 n의 길이까지 s가 반복되므로 n 을 s로 나눈 몫을 구한다.

 4. 반복되다가 마지막에는 나누어 떨어지거나 짤리거나 하니 나머지 문자열을 구한다.

   즉 'abc' 가 7 길이까지 반복되면 'abc' + 'abc'+ 'a'  가 될것이고 'bc'는 짤린다. 따라서 짤린 문자열 'a' 를 구하는 것

 5. 3번에서 구한 몫에 2번에서 몇번 반복되는지를 곱하고, 맨 마지막에 짤린 문자열에서 다시 'a' 가 몇번 반복됐는지를 구하고 더하면 끝

 

long long repeatedString(string s, long long n) {
    const char searchKey = 'a';
    const long countInString = count(s.begin(), s.end(), searchKey);
    const size_t stringLength = s.length();
    const auto repeatCnt = n / stringLength;
    const auto c = n - (repeatCnt * stringLength);

    const auto subStr = s.substr(0, c);
    const long countInSubStr = count(subStr.begin(), subStr.end(), searchKey);

    const long long ret = (repeatCnt * countInString) + countInSubStr;
    return ret;
}

 

생각해 볼 점

 1. vs2017에서 long long 을 안쓰니까 주어진 n 범위 1<= n <= 10^12 오버플로우가 난다.

 2. 변수명도 신경써야 하나?