#16172 나는 친구가 적다 (Large)
난이도 : 골드 2
유형 : 문자열 / kmp
▸ 문제
친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. 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 문자열 매칭
부분 일치 테이블로 문자열 매칭을 탐색할 때 점프를 할 수 있어 굉장히 효율적으로 연산을 수행할 수 있다.
- parent의 i = 0, pattern의 idx = 0부터 탐색을 시작한다.
- if(parent.charAt(i) == pattern.charAt(idx)) 만약 두 문자열이 일치하면 idx를 증가시킨다.
- 만약 idx == pattern의 길이와 일치한다면 문자열 매칭이 완료되었으므로 종료한다.
- while(idx > 0 && parent.charAt(i) != pattern.charAt(idx)) 문자열이 한 글자 이상 매칭된 상태에서 더 이상 글자가 불일치할 경우 현재 대응된 idx를 table[idx-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;
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 1595번 북쪽나라의 도로 (Java) (0) | 2022.03.14 |
---|---|
[BOJ] 백준 1414번 불우이웃돕기 (Java) (2) | 2022.03.13 |
[BOJ] 백준 9177번 단어 섞기 (Java) (0) | 2022.03.11 |
[BOJ] 백준 2800번 괄호 제거 (Java) (0) | 2022.03.10 |
[BOJ] 백준 7490번 0 만들기 (Java) (0) | 2022.03.09 |