IOIOI
백준 5525번 문제
https://www.acmicpc.net/problem/5525
1. 문제
2. 풀이
2.1 KMP 알고리즘
2.1.1 아이디어
이 문제는 주어진 문장열에서 특정 문자열이 몇 개나 있는지를 찾는 문제이다.
이 문제는 다음과 같이 단순하게 문자열의 단어를 처음부터 비교하는 것으로 해결할 수 있다.
주어진 각 문자열이 다음과 같다고 하자.
[단어 찾기 그_1]
[단어 찾기 그_2]
문자열의 처음부터 찾으려는 문자열의 처음과 비교한다.
위와 같이 단어가 일치하지 않는다면 다음 문자부터 다시 비교한다.
[단어 찾기 그_3]
[단어 찾기 그_4]
[단어 찾기 그_5]
[단어 찾기 그_6]
[단어 찾기 그_7]
이런식으로 문자열의 모든 위치에서 단어를 비교하면 우리가 찾는 특정 문자열이 비교되고 있는 문자열에 있는지 없는지를 파악할 수 있다.
하지만 이 방식은 시간복잡도가 O(NM)으로 비효율적이다.
위의 방식에서는 문자열의 문자를 비교하며 문자가 틀렸다는 정보만을 파악하고 다음 문자를 비교했다.
각 문자열을 비교할 때 틀렸다는 정보 외에도 일치했다는 정보를 활용할 수는 없을까?
예를 들어 앞의 예시에서 문자열의 첫 부분부터 단어를 비교했을 때를 보자.
[틀린정보 활용 그_1]
여기서 비교하는 문자가 틀려서 문자열의 다음으로 넘어가기 전에 일치했던 부분을 다시 확인해 보자.
[틀린 정보 활용 그_2]
일치했던 부분을 보면 두 번째까지의 접두사와 접미사가 일치하는 것을 알 수 있다.
이 정보를 활용하면 문자열의 두 번째부터 다시 비교하지 않을 수 있다.
[틀린 정보 활용 그_3]
두 번째까지 접두사와 접미사가 같기 때문에 위와 같이 문자열의 세 번째 위치부터 네 번째까지 총두 개의 문자가 일치한다는 사실을 알 수 있다. 때문에 우리는 이 정보를 가지고 비교되는 문자열의 다섯 번째부터 단어를 비교하면 된다.
이와 같이 각 문자열을 비교했을 때 일치했었던 부분의 정보까지 활용해서 단어를 찾는 방법이 KMP 알고리즘의 주요 아이디어이다.
위 예시와 같이 KMP 알고리즘을 사용하기 위해서는 문자열의 부분문자열 중 접두사=접미사가 될 수 있는 가장 긴 부분 문자열을 파악해야 된다.
2.1.2 p 배열 구하기
p[i]를 0~i 까지의 부분 문자열 중에서 접두사=접미사가 될 수 있는 가장 긴 부분문자열이라고 하자.
다음과 같은 표를 통해서 p[i]를 파악할 수 있다.
[p[i] 표]
문자열이 주어졌을 때 p[i] 배열은 어떻게 구할까?
가장 단순한 방법은 문자열의 첫 부분부터 하나하나씩 비교하는 것이다.
여기서는 예시를 돕기 위해 "ABAABAB"의 p[i]를 구해본다.
[p[i] 배열 구하기 그_1]
[p[i] 배열 구하기 그_2]
[p[i] 배열 구하기 그_3]
[p[i] 배열 구하기 그_4]
[p[i] 배열 구하기 그_5]
이런 식으로 문자와 문자를 처음부터 비교해 가며 p[i] 배열을 구할 수도 있지만 이래서야 앞서 문자열에서 특정 문자열을 찾기 위해 문자열의 처음부터 하나씩 문자를 비교 탐색하던 방법과 같이 비효율적이게 된다.
그래서 p[i] 배열을 구할 때도 문자가 일치했던 정보를 사용한다.
앞서 예시를 더 진행해 보자.
[p[i] 배열 구하기 그_6]
첫 번째 문자열의 7(i)번째와 두 번째 문자열의 4(j)번째 문자가 불일치했다.
여기서 i(7)를 5로 j(4)를 1로 돌려서 다시 비교해야 할까?
답은 '아니다' 이다.
우리는 두 번째 문자열의 3(j)번째 까지 첫 번째 문자와 일치했음을 알고 있다.
그리고 p[3] = 1이다.
이 말은 일치한 부분 문자열(ABA)중 접두사와 접미사가 일치하는 가장 긴 문자열의 길이가 1임을 의미한다.
때문에 첫 번째 문자열의 6(i)번째와 두 번째 문자열의 1(j)번째 문자가 일치함을 알고 있다.
위 정보를 토대로 다음과 같이 문자열을 하나씩 넘어가지 않고 중간 과정을 생략할 수 있다.
[p[i] 배열 구하기 그_7]
i = 7로 첫 번째 문자열의 마지막까지 왔기 때문에 여기서 탐색을 멈추고 p[i] 배열을 완성시킬 수 있다.
p[i]를 구하는 코드는 다음과 같다.
[caculateP]
private static void calculateP(int[] p, String target) {
int j = 0;
for (int i = 1; i < target.length(); i++) {
while (j > 0 && target.charAt(i) != target.charAt(j)) {
j = p[j - 1];
}
if (target.charAt(i) == target.charAt(j)) {
p[i] = ++j;
}
}
}
위의 예시와 같이 i는 비교되는 문자열(target)의 문자위치를 뜻하고 j는 비교하는 문자열(target)의 위치를 의미한다.
탐색은 i가 마지막 인덱스까지 갈 때까지 탐색한다.
i와 j 위치의 문자를 비교하며 틀렸을 경우 j = [p - 1]로 되돌린다.
만약 i와 j 위치의 문자가 또 틀리다면 j = [p - 1]로 되돌린다.
이를 j가 첫 번째(=0)가 될 때까지 반복한다. 코드에서는 while문으로 구현되었다.
만약 i와 j 위치의 문자가 일치할 경우 p[i] = j + 1로 기록한다.
위의 코드를 토대로 "ABABABAC"의 p[i] 배열을 구해보면 다음과 같다.
[p[i] 배열 구하기 그_8]
문자가 불일치하고 j = 0이므로 i = 2부터 다시 비교한다.
[p[i] 배열 구하기 그_9]
문자가 일치하기 때문에 p[2] = 0 + 1로 기록한다.
[p[i] 배열 구하기 그_10]
연속해서 문자가 일치하기 때문에 p[i]를 기록한다.
[p[i] 배열 구하기 그_11]
문자가 틀렸으니 j = p[4]로 돌아가서 다시 비교한다.
[p[i] 배열 구하기 그_12]
문자가 틀렸으니 j = p[2]로 돌아가서 다시 비교한다.
[p[i] 배열 구하기 그_13]
문자가 틀렸으니 j = p[0]로 돌아가서 다시 비교한다.
[p[i] 배열 구하기 그_14]
문자가 틀렸고 j = 0으로 문자열의 첫 번째이기 때문에 p[7]은 0이 된다.
2.1.3 KMP 알고리즘을 사용해서 문자열에서 문자 찾기
부분문자열의 접두사와 접미사가 같은 가장 긴 부분문자열의 길이를 알았으니 이를 토대로 문자열에서 특정 문자열을 찾는다.
코드는 다음과 같다.
[countWordByKMP]
private static int countWordByKMP(int[] p, String string, String target) {
int count = 0;
int j = 0;
for (int i = 0; i < string.length(); i++) {
while (j > 0 && string.charAt(i) != target.charAt(j)) {
j = p[j - 1];
}
if (string.charAt(i) == target.charAt(j)) {
if (j == target.length() - 1) {
count++;
j = p[j];
} else {
j++;
}
}
}
return count;
}
i는 주어진 문자열의 위치를 뜻하며 j는 찾으려는 문자열인 target의 위치를 의미한다.
앞선 예시에서 나왔던 것과 같이 비교한 문자가 틀리면 다음 문자로 하나씩 넘어가는 것이 아니라 p[i]배열을 활용해 중간 단계를 건너뛴다.
문자가 일치하고 target과 일치하는 부분문자열이 있다면 count를 +1 해준다.
이 경우에도 문자열의 다음 문자로 넘어가는 게 아니라 p 배열을 활용해 중간단계를 건너뛴다.
이와 같은 방식으로 count를 구해 문자열에 찾으려는 문자열이 몇 개 존재하는지를 구한다.
위 코드에 대한 예시는 다음과 같다.
[KMP예 그_1]
[KMP예 그_2]
j = 4 에서 문자가 일치하지 않았으므로 j = p[3] = 2로 한 후 i = 4 부터 다시 비교를 진행한다.
[KMP예 그_3]
j = 2 에서 문자가 일치하지 않았으므로 j = p[1] = 0으로 한 후 i = 4 부터 다시 비교를 진행한다.
[KMP예 그_4]
j = 0이고 문자가 일치하지 않았기 때문에 i를 +1 해주고 다시 비교를 시작한다.
[KMP예 그_5]
j의 마지막 열까지 문자가 일치했으므로 count에 1을 더해준다.
추가로 j = p[4] = 3으로 한 후 현재 i에 1을 더한 i = 10과 비교를 시작한다.
[KMP예 그_6]
i가 마지막 문자에 도달했기 때문에 탐색을 종료한다.
3. 전체 코드
[전체 코드]
import java.io.*;
public class IOIOI_5525 {
private static void calculateP(int[] p, String target) {
int j = 0;
for (int i = 1; i < target.length(); i++) {
while (j > 0 && target.charAt(i) != target.charAt(j)) {
j = p[j - 1];
}
if (target.charAt(i) == target.charAt(j)) {
p[i] = ++j;
}
}
}
private static int countWordByKMP(int[] p, String string, String target) {
int count = 0;
int j = 0;
for (int i = 0; i < string.length(); i++) {
while (j > 0 && string.charAt(i) != target.charAt(j)) {
j = p[j - 1];
}
if (string.charAt(i) == target.charAt(j)) {
if (j == target.length() - 1) {
count++;
j = p[j];
} else {
j++;
}
}
}
return count;
}
private static String createIO(int n) {
StringBuilder sb = new StringBuilder();
sb.append('I');
for (int i = 0; i < n; i++) {
sb.append("OI");
}
return sb.toString();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String word = createIO(n);
int sentenceLength = Integer.parseInt(br.readLine());
String sentence = br.readLine();
int[] p = new int[word.length()];
calculateP(p, word);
int count = countWordByKMP(p, sentence, word);
bw.write(String.valueOf(count));
bw.flush();
}
}
댓글