[백준] 1786번: 찾기 - JAVA

🔗 문제 링크

BOJ 1786번: 찾기

1786번: 찾기

 

📝 풀이 과정

주어진 문자열(T)에서 패턴 문자열(P)를 찾아 인덱스를 구하면 되는 간단한 문제이다.
하지만, 범위가 각각 $1,000,000 = 10^6$이므로 단순하게 문자열을 찾는 이중반복문으로 문제를 해결하려고 하면 $O(NM) = 10^{12}$으로 시간초과가 발생하게 된다.

 

따라서, 효율적으로 문자열을 찾는 알고리즘인 KMP 알고리즘을 사용해야 한다.
처음 문제를 풀 때, 기존 KMP에서 인덱스를 저장하는 방식인 ArrayList.add방식을 사용했는데 시간이 약 5000ms가 소요되어 시간을 줄이기 위해 cnt변수와 StringBuilder를 사용해 인덱스의 수와 인덱스를 각각 저장하여 출력하는 방식으로 변경하였다.

 

⏱ 시간 복잡도

KMP 알고리즘의 시간복잡도는 $O(N+M)$이므로, 최악의 경우 2,000,000이지만 제한 시간을 초과하지 않는다.

 

💻 코드

import java.util.Scanner;

public class Main {
    static int cnt = 0;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String T = sc.nextLine();
        String P = sc.nextLine();

        kmp(T, P);
        System.out.println(cnt);
        System.out.println(sb);
    }

    public static int[] getPi(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];

        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
                j = pi[j - 1];

            if (pattern.charAt(i) == pattern.charAt(j))
                pi[i] = ++j;
        }

        return pi;
    }

    public static void kmp(String parent, String pattern) {
        int[] pi = getPi(pattern);

        int n = parent.length(), m = pattern.length();

        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && parent.charAt(i) != pattern.charAt(j))
                j = pi[j - 1];

            if (parent.charAt(i) == pattern.charAt(j)) {
                if (j == m - 1) {
                    cnt++;
                    sb.append(i - m + 2).append('\n');
                    j = pi[j];
                } else j++;
            }
        }

    }
}

 

 

📊 제출 결과