[BOJ] 백준 16172번 나는 친구가 적다 (Large) (Java)

#16172 나는 친구가 적다 (Large)

난이도 : 골드 2

유형 : 문자열 / kmp

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

▸ 문제

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

▸ 입력

첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 200,000)

단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.

▸ 출력

첫 번째 줄에 성민이가 찾고자 하는 키워드가 교과서 내에 존재하면 1, 존재하지 않으면 0을 출력한다.

 

문제 풀이  

선형시간으로 두 문자열이 일치하는지 찾으려면 O(S*K) =  최대 400억의 연산이 필요하다. 그래서 kmp 매칭 문자열 알고리즘을 사용하는 것이다.  kmp 알고리즘은 매칭 문자를 찾는 연산 횟수를 줄이기 위해서 반복되는 연산을 줄여나가 매칭 문자열을 빠르게 점프하는 기법이다. 이 알고리즘을 사용하면 O(S+K)의 시간복잡도로 해결이 가능하다. 

 

해당 문제는 주어진 parent(S)에 숫자를 모두 제거한 후 kmp 알고리즘을 수행해주면 되는 기본적인 kmp 알고리즘 문제이다. 먼저 숫자를 모두 제거하기 위해서는 String 클래스에 있는 replaceAll("[0-9]", "") 메서드를 사용하면 간단히 없앨 수 있다.

 

부분 일치 테이블 구하기

kmp 알고리즘에서 가장 중요한 부분은 부분 일치 테이블을 구하는 것이다

• table[i] = pattern(0...i)의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

예를 들어, abacaaba가 있을 때 다음과 같이 구할 수 있다.

 

i	pattern(0...i)	접두사이면서 접미사인 최대 문자열	table[i]
0	a	(없음)	0
1	ab	(없음)	0
2	aba	a	1
3	abac	(없음)	0
4	abaca	a	1
5	abacaa	a	1
6	abacaab	ab	2
7	abacaaba	aba	3

 

KMP 문자열 매칭 

부분 일치 테이블로 문자열 매칭을 탐색할 때 점프를 할 수 있어 굉장히 효율적으로 연산을 수행할 수 있다.

1. parent의 i = 0, pattern의 idx = 0부터 탐색을 시작한다.
2. if(parent.charAt(i) == pattern.charAt(idx)) 만약 두 문자열이 일치하면 idx를 증가시킨다.
   1. 만약 idx == pattern의 길이와 일치한다면 문자열 매칭이 완료되었으므로 종료한다.
3. while(idx > 0 && parent.charAt(i) != pattern.charAt(idx))  문자열이 한 글자 이상 매칭된 상태에서 더 이상 글자가 불일치할 경우 현재 대응된 idx를 table[idx-1]로 줄인다.
   
   1. 이 부분이 중요한데 문자열 매칭이 시작된 후 연속적인 매칭이 이뤄지지 않을 때 다시 매칭을 시작해야하는 시점이다. 다시 매칭을 idx = 0부터 시작하는 것이 아닌 문자열 매칭된 부분이 접두사와 접미사가 일치하는 구간이라면 idx = 0이 아닌 그 일치하는 구간 다음의 idx 값을 받게 된다. 그래서 앞 접두사 부분을 생략하고 빠르게 탐색이 가능해진다.

static boolean kmp(String parent, String pattern) {
	int[] table = makeTable(pattern);
	
	int n1 = parent.length();
	int n2 = pattern.length();
	
	int idx = 0;
	for(int i=0; i<n1; i++) {
		while(idx > 0 && parent.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
		
		if(parent.charAt(i) == pattern.charAt(idx)) {
			if(idx == n2-1) {
				idx = table[idx];
				return true;
			}else {
				idx++;
			}
		}
	}
	return false;
}

 

KMP 알고리즘에 대해 더 자세히 알고싶다면 여기를 참고해주세요.

 

풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String parent = br.readLine().replaceAll("[0-9]", "");
		String pattern = br.readLine();
	
		System.out.println(kmp(parent, pattern) ? 1 : 0);
	}
	
	static boolean kmp(String parent, String pattern) {
		int[] table = makeTable(pattern);
		
		int n1 = parent.length();
		int n2 = pattern.length();
		
		int idx = 0;
		for(int i=0; i<n1; i++) {
			while(idx > 0 && parent.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(parent.charAt(i) == pattern.charAt(idx)) {
				if(idx == n2-1) {
					idx = table[idx];
					return true;
				}else {
					idx++;
				}
			}
		}
		return false;
	}
	
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		
		int idx = 0;
		for(int i=1; i<n; i++) {
		
			while(idx > 0 && pattern.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				idx ++;
				table[i] = idx;
			}
		}
		
		return table;
				
	}
}