[SWEA] 4038. [Professional] 단어가 등장하는 횟수 (with JAVA)

문제 4038

SW Expert Academy

 

처음에는 정말 단순한 방법으로 하나씩 비교해가며 풀었습니다. 당연하게 시간초과가 났고, 좀 더 효율적으로 푸는 알고리즘인 KMP 알고리즘을 활용하여 해결하였습니다.

KMP 알고리즘을 살펴보기에 앞서, 단순하게 비교하며 푸는 방법에서 어떤 부분을 효율적으로 개선시켜야 하는지에 대해 알아보겠습니다.

탐색할 문자열이 "ababa" 일 때, "aba" 가 몇 번 들어가는지를 알아보려고 합니다. 아래는 제가 처음에 풀었던 방식입니다.

안들어감

안들어감

1번 들어감

안들어감

안들어감

2번 들어감

안들어감

 

이렇게 해서 총 2번이 들어가는 것을 확인할 수 있지만, 총 7번에 걸쳐서 찾을 수 있었습니다. 즉, 찾으려는 단어의 길이가 M 이고 문자열의 길이가 N 일 때, 시간복잡도가 O(MN) 이 됩니다.

그럼 KMP 알고리즘은 어느 부분을 효율적으로 한 것일까요? 맨 처음 단어를 비교했을 때, 단순하게 문자열이 다르다는 것 이외에 또 발견할 수 있는 것이 있습니다. 바로 sentence[2] ~ sentence[3] 와 pattern[0] ~ pattern[1] 이 같다는 것입니다. 이를 통해서 문자열이 다르다고 판단 후, 바로 다음 인덱스 1로 넘어가는 것이 아니라 인덱스 2로 넘어갈 수 있습니다.

sentence[0] ~ sentence[1] == pattern[0] ~ pattern[1]

인덱스 2로 바로 넘어감

따라서 sentence 의 접미사와 pattern 의 접두사가 일치하면 그 사이의 중간 부분을 건너 뛰고 탐색하면 됩니다. 그러면 pattern 의 접두사와 접미사가 일치하는 길이를 저장하는 배열(table)이 필요합니다.

 

위의 내용들을 바탕으로 아래와 같이 로직을 구현하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int test_case = 1; test_case <= T; test_case++) {
            String B = br.readLine();
            String S = br.readLine();
            int[] table = new int[S.length()];
            int cnt = 0;
            int idx = 0;

            for (int i=1; i<S.length(); i++) {
                // 맞는 위치가 나올 때까지 이동
                while (idx > 0 && S.charAt(i) != S.charAt(idx)) {
                    idx = table[idx-1];
                }

                if (S.charAt(i) == S.charAt(idx)) { // 맞을 경우
                    idx += 1;
                    table[i] = idx;
                }
            }

            idx = 0;
            for (int i=0; i<B.length(); i++) {
                while (idx > 0 && B.charAt(i) != S.charAt(idx)) {
                    idx = table[idx-1];
                }

                if (B.charAt(i) == S.charAt(idx)) { // 맞을 경우
                    if (idx == S.length()-1) {
                        cnt++;
                        idx = table[idx];
                    } else {
                        idx++;
                    }
                }
            }

            sb.append("#").append(test_case).append(" ").append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}