자바 코딩테스트 강좌, 문자열 찾기

문제 설명

주어진 문자열에서 특정 패턴의 문자열이 몇 번 등장하는지를 찾는 문제입니다.
예를 들어, 문자열 "banana"에서 패턴 "ana"가 몇 번 나타나는지를 구하는 것입니다.

입력

문자열 text: 검색할 전체 문자열 (1 ≤ |text| ≤ 100,000)
문자열 pattern: 찾을 문자열 (1 ≤ |pattern| ≤ 50)

출력

문자열 text에서 pattern이 나타나는 총 횟수를 반환합니다.

예제

입력

text = "banana"
pattern = "ana"

출력

문제 풀이 과정

이 문제를 해결하기 위해서는 문자열 검색 알고리즘을 사용해야 합니다.
가장 간단한 방법은 문자열을 한 글자씩 순회하며 패턴을 비교하는 방법이지만,
이는 효율적이지 않아 대규모 데이터에서 시간 복잡도가 O(n*m)으로 비효율적입니다.

효율적인 해결책: KMP 알고리즘

문자열 검색 문제를 효율적으로 해결할 수 있는 방법 중 하나는 KMP(Knuth-Morris-Pratt) 알고리즘을 사용하는 것입니다.
이 알고리즘은 다음과 같은 두 부분으로 구성되어 있습니다:

패턴을 기반으로 한 ‘LPS(Longest Prefix which is also Suffix)’ 배열을 생성합니다.
텍스트를 순회하며 패턴을 비교하면서 LPS 배열을 활용합니다.

LPS 배열 생성

LPS 배열은 패턴 내에서 접두사와 접미사가 얼마나 일치하는지를 나타냅니다. 이를 통해 패턴을 재사용하면서 검색할 수 있습니다.
예를 들어, 패턴이 "ABAB"이라면 LPS 배열은 [0, 0, 1, 2]입니다.

알고리즘 구현

이제 위 과정을 바탕으로 문자열 찾기 알고리즘을 자바로 구현해보겠습니다.

public class KMP {
    public static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0; 
        int i = 1;
        
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int KMPsearch(String text, String pattern) {
        int[] lps = computeLPS(pattern);
        int i = 0; 
        int j = 0; 
        int count = 0;

        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;

                if (j == pattern.length()) {
                    count++;
                    j = lps[j - 1];
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String text = "banana";
        String pattern = "ana";
        int result = KMPsearch(text, pattern);
        System.out.println("Substring Count: " + result);
    }
}

코드 설명

위 코드는 KMP 알고리즘을 구현한 것으로 두 개의 주요 함수가 있습니다.
computeLPS 함수는 패턴에 대한 LPS 배열을 생성하고, KMPsearch 함수는 텍스트에서 패턴을 검색하며 일치하는 개수를 세는 역할을 합니다.

복잡도 분석

KMP 알고리즘의 시간 복잡도는 O(n + m)입니다. 여기서 n은 텍스트의 길이, m은 패턴의 길이입니다.
이는 패턴이 텍스트 내에서 이동하고 재사용되기 때문에 가능한 효율적인 방법입니다.

마무리

오늘은 문자열 검색 문제를 해결하기 위한 KMP 알고리즘에 대해 살펴보았습니다.
이 알고리즘을 사용하면 다양한 문자열 검색 문제를 효율적으로 해결할 수 있습니다.
문제를 접하면서 다양한 알고리즘을 시도해 보시고 실력을 쌓아보세요!