[종만북] 문제: JAEHASAFE
문제
길이가 최대 10,000인 문자열이 N+1(1 ≤ N ≤ 100) 개 주어진다.
각 문자열은 다이얼의 상태를 나타내며, 서로 다른 순서로 정렬된 문자의 집합이다.
초기 상태에서 시작하여, 주어진 순서대로 문자열을 맞추기 위해 오른쪽(시계 방향) 또는 왼쪽(반시계 방향) 회전을 수행할 수 있다.
목표는 주어진 순서대로 다이얼을 맞추기 위해 수행해야 하는 최소 회전 횟수의 합을 계산하는 것이다.
서론
KMP알고리즘이 무엇인지 배웁니다.
문자열을 찾는 문제이나, 이번에는 회전 문자열(Circular string)에 대해 KMP알고리즘을 적용시켜봅시다.
KMP 알고리즘
KMP알고리즘을 바로 이해하는 것은 어렵고 설명 또한 복잡하기 때문에..
인터넷에 있는 양질의 글로 설명을 대체합니다.
KMP 알고리즘 설명1 (개인적으로 이 글이 제일 맘에 들었다.)
KMP 알고리즘의 의의
쉽게 생각하면 어떤 String 두 개를 매칭하는 알고리즘을 작성하려고 하면, 이를 naive방식으로 작성 시 $O(n^2)$시간이 걸립니다.
하지만, naive한 알고리즘에서 버려지는 정보를 극한으로 활용해 $O(n)$시간에 문자열에 대한 탐색을 할 수 있게 하는 것이 KMP알고리즘입니다.
회전(Circular)관련 문제를 푸는 팁
먼저 찾으려고 하는 string을 $Needle$로 정의, 그 대상이 되는 string을 $Haystack$으로 정의합니다.
이렇게 회전하는 대상이 있으면, 그냥 그 대상을 옆에 이어 붙인 형태로 생각하는 게 좋습니다.
따라서 문제를 조금 변형하면, string $Haystack + Haystack$에서 $Needle$을 찾는 것이됩니다.
단, $\vert Haystack \vert$ 이후의 $index$에서 $Needle$을 찾으면 안됩니다. (Circular 이므로)
알고리즘 구상
KMP를 이용한 탐색 함수
문제를 정의하면, 문자열 $Haystack$ 안에서 문자열 $needle$이 나타나는 시작 위치를 찾는 것입니다.
H[(begin + i) % sizeN]처럼 원형 인덱스를 활용하여 $Haystack$에 별도로 추가 연산을 하지 않는다.- 실패 함수
pi[]를 작성한다. (KMP알고리즘)
KMP가 동작하기 위한 실패함수
pi[i]는 문자열needle[0..i]의 접두사(Prefix) 이자 접미사(Suffix)가 될 수 있는 최대 길이를 나타낸다.i번 문자까지 확인했을 때, 어디까지 일치했는지를 빠르게 알기 위해 필요합니다.
pi[]는 다음과 같은 과정을 통해 채울 수 있습니다.
이것에 대한 과정은 KMP알고리즘 설명에 의해 자세히 나와있으니 간략히 설명하겠습니다.
begin = 1, i = 0에서 시작needle[begin + i]와needle[i]가 같으면i++후pi[begin + i - 1] = i- 다르면,
i == 0이면begin++(새로운 시작 위치)- 그렇지 않으면
begin += (i - pi[i-1]),i = pi[i-1]
알고리즘 설계
과정을 간략히 정의하면 이렇습니다.
- $Haystack$와 $Needle$을 각 경우에 따라 정의한다.
- 실패함수
pi[]를 구한다. pi[]를 통해 $Haystack$에서 $Needle$을 찾는다.
알고리즘 구현
failure()
pi[]를 채우는 코드를 작성합니다. 설명은 생략하겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void failure() {
int begin = 1, i = 0;
while (begin + i < sizeN) {
if (needle[begin + i] == needle[i]) {
i++;
pi[begin + i - 1] = i;
} else {
if (i == 0) {
begin++;
} else {
begin += i - pi[i - 1];
i = pi[i - 1];
}
}
}
}
findKMP()
앞서 설명한 실패함수를 이용해 문자열의 $index$를 찾는 함수를 정의합니다.
최소 $index$만 찾으면 되므로, 찾았다면 함수를 종료합니다.
포인트는, H[(begin + i) % sizeN] == needle[i]으로 문자열을 따로 추가하지 않고도 탐색할 수 있게 구현합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void findKMP() {
int begin = 1, i = 0;
while (begin < sizeN) {
if (i < sizeN && H[(begin + i) % sizeN] == needle[i]) {
i++;
if (i == sizeN) {
ret = begin;
return;
}
} else {
if (i == 0) {
begin++;
} else {
begin += i - pi[i - 1];
i = pi[i - 1];
}
}
}
}
main()
다이얼을 오른쪽으로 왼쪽으로 번갈아가며 회전하는 것을 구현하려면
findKMP()를 시계 방향과 반시계 방향을 따로 구현해야합니다.
하지만 경우에 따라 $Haystack$와 $Needle$을 번갈아가며 정의하면, findKMP()의 시계 방향만 구현해도 문제를 풀 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
fastIO;
int C;
cin >> C;
while (C--) {
cin >> n >> needle;
sizeN = needle.size();
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> cache;
if (i % 2 == 0) {
H = move(cache);
} else {
needle = move(cache);
}
failure();
findKMP();
sum += ret;
}
cout << sum << "\n";
}
return 0;
}
최종 코드
여기에서 확인하세요!