[Algorithm] Hackerrank - Repeated String

문제:

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  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.

 

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.

 

코드:

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the repeatedString function below.
def repeatedString(s, n):
    if s.count('a') == 0:
        return 0
    elif len(s) == 1 and s=='a':
        return n
    else:
       return s.count('a') * int(n/len(s)) + s[:n%len(s)].count('a')

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    n = int(input())

    result = repeatedString(s, n)

    fptr.write(str(result) + '\n')

    fptr.close()

 

설명:

일단 주어진 s스트링을 반복해서 붙혀서 n만큼 잘라낸다음 a 의 수를 샌다는건데

제일 처음엔 단순하게 str(s*n).count('a') 로 실행했다가 몇몇 케이스에서 시간오버로 에러가 떳다.

 

따라서 다른방법이 필요한대...

일단 그래서 주어진 s스트링에서 a의 수를 센다음에

주어진 n만큼 s를 나눈다 -> 결국엔 반복된 문자열에 a를 카운트를 할수있는것

 

이후 n/s 의 나머지는 문자열 s를 나머지 만큼 잘라낸다음 a를 세면 된다.

 

설명을 쓰다보니 왜 처음방법을 저렇게 했는지 이해가 안되는구만 절레절레 도대체 왜곱한거지ㅋㅋㅋㅋㅋㅋㅋ