[HackerRank] Repeated String (Python)

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a's in the first n letters of Lilah's infinite string.

For example, if the string s = 'abcac' and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of a in the substring.

 

Function Description

Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a in the prefix of length n in the infinitely repeating string.

repeatedString has the following parameter(s):

• s: a string to repeat
• n: the number of characters to consider

Input Format

The first line contains a single string, s.
The second line contains an integer, n.

 

Constraints

• 1 <= | s | <= 100
• 1 <= n <= 10^12
• For 25% of the test cases, n < 10^6.

Output Format

Print a single integer denoting the number of letter a's in the first n letters of the infinite string created by repeating s infinitely many times.

 

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0
The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a's, we print 7 on a new line.

 

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1
Because all of the first n = 1000000000000 letters of the infinite string are a, we print 1000000000000 on a new line.

 

첫번째 시도

from collections import Counter
import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def getFrequencyA(my_string):
    count = dict(Counter(my_string))

    keys = count.keys()

    if 'a' in keys:
        answer = count['a']
    else:
        answer = 0
    return answer

def repeatedString(s, n):
    if len(s) == 1 and s != 'a':
        answer = 0
    elif len(s) == 1 and s == 'a':
        answer = n
    elif len(s) > n:
        new_string = list(s[:n])
        
        answer = getFrequencyA(new_string)
    else:
        loop_num = n // len(s)
        mod_num = n % len(s)

        new_string = ''

        for i in range(loop_num):
            new_string = new_string + s
        new_string = new_string + s[:mod_num]

        new_string = list(new_string)

        answer = getFrequencyA(new_string)

    return answer

첫번째 시도 풀이

입력받은 문자열의 길이가 1이고 그 문자열이 a 가 아닐경우 0을 answer에 넣어줍니다.

입력받은 문자열의 길이가 1이고 그 문자열이 a 일 경우 a가 나올 수 있는 최대의 개수인 n을 정답 answer에 넣어줍니다.

입력받은 문자열의 길이가 n보다 클 경우에 n까지의 데이터만 추출한 후 

collections의 Counter를 활용하여 a 가 몇개있는지 확인한 후 answer에 넣어줍니다.

입력받은 문자열의 길이가 n보다 작거나 같을 경우 n 길이의 문자열을 입력받은 문자열로 만들어주고

그 문자열에서 a가 몇개있는지 동일하게 확인한 후 answer에 넣어줍니다.

 

결과

런타임 에러가 났습니다.

 

왜 그런지 엄청 큰 숫자와 긴 문장을 넣으니

73억번의 loop를 도느라 약 35분의 시간이...

 

어떻게 하면 저 시간을 줄일 수 있을까 고민해보았습니다.

 

for 반복문을 사용하는 부분은 

입력받은 문자열의 길이가 n보다 작거나 같을 경우 n 길이의 문자열로 다시 만드는 경우!

생각해보니 굳이 그 길이의 문자열을 다 만들고 시작하지 않고

입력받은 문자열 안에있는 a 의 개수와

뒤에 이어붙일 문자열 안에있는 a 의 개수를 미리 구해놓고

for 반복문을 사용하지 않고 계산식을 활용하면 더 빠르게 해결할 수 있을 것 같았습니다.

 

해당 조건을 고려하여 두번째 시도를 해보았습니다.

 

두번째 시도

#!/bin/python3

from collections import Counter
from tqdm import tqdm
import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def getFrequencyA(my_string):
    count = dict(Counter(my_string))

    keys = count.keys()

    if 'a' in keys:
        answer = count['a']
    else:
        answer = 0
    return answer

def repeatedString(s, n):
    if len(s) == 1 and s != 'a':
        answer = 0
    elif len(s) == 1 and s == 'a':
        answer = n
    elif len(s) > n:
        new_string = list(s[:n])
        
        answer = getFrequencyA(new_string)
    else:
        answer = 0
        loop_num = n // len(s)
        mod_num = n % len(s)

        s_a_count = getFrequencyA(s)
        s_mod_count = getFrequencyA(s[:mod_num])

        answer = answer + (s_a_count * loop_num) + s_mod_count

    return answer

결과

무사히 통과!

 

항상 엄청나게 큰 경우를 생각하고

무조건 for 반복문을 사용하기보다 더 효율적인 방법은 없는지 생각해봐야겠다고 생각이 들었던 문제였습니다.

읽어주셔서 감사합니다!

 

SOMJANG/CODINGTEST_PRACTICE