[BOJ/Java] 1786. 찾기

[BOJ/Java] 1786. 찾기

1786번: 찾기

---

문제 해석

문자열에서 특정 패턴을 찾는 문제로, 주어진 텍스트 문자열(T)에서 패턴 문자열(P)이 등장하는 모든 위치를 찾아 그 시작 위치들을 출력하는 것이다. 이 문제는 문자열 검색 알고리즘 중 하나인 KMP(Knuth-Morris-Pratt) 알고리즘을 사용하여 해결할 수 있다. KMP 알고리즘은 불필요한 문자 비교를 최소화하여 빠른 검색을 가능하게 한다.

풀이 과정

1. 입력 받기: 문자열 T와 패턴 P를 입력 받는다.
2. KMP 실행: KMP 알고리즘의 메인 로직을 실행한다.
   • 실패 함수 생성: 패턴 P에 대한 실패 함수를 생성한다. 이 함수는 패턴 내에서 불일치가 발생했을 때, 어느 위치로 점프할지 결정한다.
   • 검색 함수: 실패 함수를 사용하여 전체 텍스트 T에서 패턴 P를 검색한다.
3. 결과 출력: 검색 결과로 나온 패턴의 위치와 개수를 출력한다.

코드

import java.io.*;

public class Main {
    private static char[] T, P; // 텍스트와 패턴을 저장할 배열
    private static int[] F; // 실패 함수를 저장할 배열
    private static StringBuilder ans = new StringBuilder(); // 결과 위치를 저장할 StringBuilder
    private static int cnt = 0; // 패턴이 나타난 횟수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        T = br.readLine().toCharArray(); // 텍스트 T를 입력받음
        P = br.readLine().toCharArray(); // 패턴 P를 입력받음

        KMP(); // KMP 알고리즘 실행

        sb.append(cnt).append("\n"); // 패턴이 나타난 횟수 출력
        sb.append(ans.toString()); // 모든 위치 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void KMP() {
        getFailureFunction(); // 실패 함수를 생성
        search(); // 텍스트에서 패턴 검색
    }

    private static void getFailureFunction() {
        F = new int[P.length];
        int i = 1, j = 0;

        while (i < P.length) {
            if (P[i] == P[j]) F[i++] = ++j; // 패턴 내에서 일치하는 경우
            else if (j > 0) j = F[j - 1]; // 불일치시 이전 일치 지점으로 점프
            else i++; // 일치하는 부분이 전혀 없는 경우
        }
    }

    private static void search() {
        int i = 0, j = 0;
        while (i < T.length) {
            if (T[i] != P[j]) {
                if (j > 0) j = F[j - 1]; // 불일치시 실패 함수에 따라 점프
                else i++;
            } else {
                if (j == P.length - 1) { // 패턴이 완전히 일치하는 경우
                    ans.append(i - j + 1).append(" "); // 위치 저장
                    cnt++; // 카운트 증가
                    j = F[j]; // 다음 검색을 위해 점프
                } else j++;
                i++;
            }
        }
    }
}

시간 복잡도 분석

KMP 알고리즘의 시간 복잡도는 O(n + m)이다. 여기서 n은 텍스트 T의 길이, m은 패턴 P의 길이이다. 실패 함수를 계산하는 데 O(m)의 시간이 소요되고, 검색 과정에서는 O(n)의 시간이 소요된다.

느낀점

KMP 알고리즘을 이용해 복잡한 문자열 검색 문제를 효율적으로 해결할 수 있었다는 점이 인상적이다. 불필요한 문자 비교를 줄이는 실패 함수의 개념을 통해 문자열 검색의 효율성을 극대화할 수 있었다.