[JAVA] 16172 나는 친구가 적다 (Large) (KMP 알고리즘)

https://www.acmicpc.net/problem/16172

16172번: 나는 친구가 적다 (Large)

 

KMP 알고리즘을 사용하여 푸는 문제이다.

 

아래는 기억하기 위한 주저리주저리

1. pi 배열을 구하는 방법과 KMP 를 구하는 방법은 동일하다.

- pi 는 비교할 배열의 앞뒤를 구분

- KMP 는 비교할 배열과 비교되는 배열

 

2. pi 배열은 i=1, j=0 부터 시작 (j 가 앞부분)

KMP는 i=0, j=0 으로 처음부터 비교

 

 

메모리 초과가 정말 많이 났는데 해결한 과정

- Scanner 도 메모리 초과를 낼 수 있다 -> BufferedReader 로 바꾸기

- char 배열도 삭제하고 charAt() 함수를 사용했는데 String 배열도 아닌지라 상관없는 것 같다.

- for 문 돌면서 숫자 제거했는데 replaceAll() 함수를 사용했더니 메모리 초과 해결!

 

이유는 String 은 불변이기 때문에 += 를 할때마다 새로운 String 을 생성해서 저장한다고 한다.

StringBuffer 의 append 를 사용하거나 함수를 이용하자

 

정규표현식도 다시 공부를!

 

 

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

public class boj16172 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S, S2, K;
        int[] pi;

        S = br.readLine();
        K = br.readLine();

        S2 = S.replaceAll("[0-9]", "");

        pi = new int[S2.length()];

        // pi 구하기
        for (int i=1, j=0; i<S2.length(); i++) {

            while (j > 0 && S2.charAt(i) != S2.charAt(j)) {
                j = pi[j-1];
            }

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

        // KMP 알고리즘 수행
        for (int i=0, j=0; i<S2.length(); i++) {

            while (j > 0 && S2.charAt(i) != K.charAt(j)) {
                j = pi[j-1];
            }

            if (S2.charAt(i) == K.charAt(j)) {
                if (j == K.length() - 1) {
                    System.out.println(1);
                    return;
                    // j = pi[j];
                }
                else {
                    j++;
                }
            }
        }

        System.out.println(0);
    }
}