Algorithmhackerrank

HackerRank Repeated String

1. HackerRank Repeated String

There is a string, , of lowercase English letters that is repeated infinitely many times. Given an integer, , find and print the number of letter a’s in the first letters of the infinite string.

Example

The substring we consider is , the first characters of the infinite string. There are occurrences of a in the substring.

Function Description

Complete the repeatedString function in the editor below.

repeatedString has the following parameter(s):

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

int: the frequency of a in the substring
Input Format

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

Constraints

For of the test cases, .
Sample Input

Sample Input 0

aba
10
Sample Output 0

7
Explanation 0
The first letters of the infinite string are abaabaabaa. Because there are a’s, we return .

Sample Input 1

a
1000000000000
Sample Output 1

1000000000000
Explanation 1
Because all of the first letters of the infinite string are a, we return .

1.1. 컴퓨팅적 사고

해당 문제는 주어진 문자열 s의 문자의 반복을 통해 n의 범위까지의 문자열을 만들고 그 중 'a’의 개수를 리턴해주는 문제입니다.

처음에 정규표현식으로 접근하였다가 올바르지 않는 솔루션인것 같아 최대 문자열의 개수를 이용하여 문제를 해결하였습니다.

문자열의 최대는 n까지이므로 n / s의 길이를 해주게 되면 s의 문자열이 몇 번 반복되는지 알 수 있습니다. 그리고 n % s로 나눈 나머지는 최대나오는 횟수를 제외한 나머지 문자열을 구할 수 있습니다.

예를 들어, s가 ‘aba’ n = 10이 주어졌다고 가정하면 s로 만들수 있는 최대의 문자열은 다음과 같습니다.

abaabaabaa 총 길이가 10이 되는 문자열이 되고, abcac로 만들 수 있는 최대 횟수는 3회가 됩니다. 그리고 최대횟수를 제외한 나머지는 a문자열 하나 즉 1개가 남게 됩니다.

  1. 문제풀이를 진행해보면 맨처음에 s라는 문자열에 'a’라는 문자열이 존재하지 않으면 더이상 솔루션을 진행할 필요가 없기 때문에 0을 리턴해주었습니다.
  2. 만약에 n의 범위보다 s의 길이가 크다면 n의 범위를 제외한 나머지범위중에서 'a’의 개수를 카운팅 시켜줍니다.
  3. 만약에 n의 범위보다 s의 길이가 작다면 s로 만들수 있는 최대의 횟수 + s의 나머지의 횟수를 구해줍니다.
    즉, ‘abaabaaba’ 길이 9 s로 만들 수 있는 최대의 횟수 3(최대 나누어진 개수) * 2(a의 개수) 와 abaabaaba를 제외하면 나머지는 1만큼만 채울 수 있기 때문에 'a’를 그 이후에 붙여나갈 수 있습니다. 따라서 나머지 a의 개수 1 을 더해주게 되면 (3 * 2 + 1) 즉, 7의 값을 도출해낼 수 있습니다.
  4. n의 범위는 n^12이므로 1000000000000 long의 범위에 주의하여 처리하면 쉽게 구할 수 있습니다.

1.2. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * 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
     */

    public static long repeatedString(String s, long n) {
        // Write your code here
        long numOfString = n / s.length();
        long remain = n % s.length();
        if(!s.contains("a")) return 0;

        long answer = 0L;
        if(s.length() > n){
            answer = counterOfString(s, remain);
        }else {
            answer = numOfString * counterOfString(s, s.length()) + counterOfString(s, remain);
        }
        return answer;
    }
     private static long counterOfString(String s, long end){
        int a = 0;
        for(int i=0; i<end; i++){
            if(s.charAt(i) == 'a'){
                a++;
            }
        }
        return a;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s = bufferedReader.readLine();

        long n = Long.parseLong(bufferedReader.readLine().trim());

        long result = Result.repeatedString(s, n);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}
Share