BOJ 2340
오랜만에 진득하게 고민해서 문제를 풀어보았습니다.
웬만하면 두어시간 고민하고 풀이를 보는 편이지만 풀이가 없어서 볼 수 없었습니다..
문제
BOJ 2340 이진 수열 회전
길이 $N$ 의 이진 수열을 회전시켜 총 $N$ 개의 수열을 만듭니다. 이를 사전순으로 정렬하고, 가장 마지막 숫자들로 새로운 수열을 얻습니다. 이때 원래의 수열을 구하는 것이 문제입니다.
회전시킨 문자열의 마지막 문자를 붙여 문자열을 만드는 변환을 BWT(Burrows–Wheeler transform) 이라고 부르며 문제는 이진 수열에서 역변환을 $O(N^2)$ 보다 빠르게 구하면 됩니다.
풀이
입력으로 주어지는 수열을 $S$, 정답을 $A$ 로 두겠습니다. 당연히도 두 수열 모두 길이는 $N$ 입니다.
가장 먼저 떠올릴 수 있는 부분은 어떤 수열 $A$ 가 정답이 될 수 있는지 판별하는 방법입니다. $A$ 를 두 번 이어붙여 길이 $2N$ 의 수열에서 접미사 배열을 구하면 $A_0, …, A_{N - 1}$ 에서 시작하는 수열들을 정렬할 수 있으며 BWT를 $O(NlogN)$ 에 구하게 됩니다. ( 접미사 배열 설명: wikipedia ) 이제 가능한 $A$ 를 구하고, BWT를 구하여 $S$ 와 일치하면 출력하고, 일치하지 않는다면 $-1$ 을 출력하면 됩니다.
다음으로 할 수 있는 관찰은 $S_0 = A_{N - 1}$ 이라는 점입니다. $A$ 는 회전시킨 수열들 중 가장 앞서는 문자열이므로, $A$ 의 마지막 문자가 $S$ 의 첫 번째 문자가 됩니다. 이제 수열 $A = A_0\, A_1\, …\, A_{N - 2}\, S_0$ 가 됩니다.
가장 중요한 부분으로, $A_{N - 2}$ 를 구해보겠습니다. $S$ 를 구할 때에 $A$ 를 오른쪽으로 한 번 회전 시킨 수열 $A’ = S_0\, A_0\, … \, A_{N - 2}$ 또한 포함되어 있습니다. 앞서 말했듯, $A$ 는 회전시킨 수열들 중 가장 앞서는 문자열이기 때문에 $A’$ 은 $S_0$ 으로 시작하는 수열들 중 사전순으로 가장 앞섭니다. $S_0$ 의 값에 따라 $A’$ 이 사전순으로 몇 번째에 위치하는지 알 수 있으며 해당 위치의 $S$ 의 값이 $A_{N - 2}$ 가 됩니다. 수식으로 나타내면 다음과 같습니다. 이때 $zcnt$ 는 $S$ 의 $0$ 의 개수입니다.
\[A'_{N-1} = A_{N - 2} = \begin{cases} S_0 & \text{$S_0 = 0$} \\ S_{zcnt} & \text{$S_0 = 1$} \\ \end{cases}\]$S_0 = 0$ 인 경우 $A’$ 이 모든 회전 수열들 중 가장 앞섭니다. $S_0 = 1$ 인 경우 $0$ 으로 시작하는 수열을 제외하고 가장 앞서므로 $zcnt$ 번째로 앞섭니다. (zero-based)
위의 과정을 바탕으로, 어떤 수열 $T$ 가 사전순으로 몇 번째에 위치하는지 안다면, 이를 오른쪽으로 한 번 회전시킨 수열 $T’$ 이 몇 번째로 앞서는지 구할 수 있습니다. 수열들을 사전순으로 보았을 때, $T_{N-1}=0$ 이라면 $T’$ 은 앞서 $0$ 으로 끝나는 수열들의 바로 다음에 순서에 위치합니다. 동일하게 $T_{N-1}=1$ 이라면 앞서 $1$ 으로 끝나는 수열들의 바로 다음에 위치합니다. 만약 $0$ 으로 끝나는 첫 수열이라면 $0$ 번째, $1$ 으로 끝나는 첫 수열이라면 $zcnt$ 번째에 위치합니다. 구현에서는 solve 함수 첫 부분에 배열 $t$ 를 채우는 부분입니다.
$A$ 를 역순으로 구성하고, BWT가 $S$ 와 일치하는지 확인하면 됩니다. 최근에 템플릿 정리를 하며 접미사 배열도 새로 구현하였습니다. 구현은 이곳에서 볼 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int N;
string S;
int t[50000];
void solve() {
cin >> N >> S;
int zcnt = 0;
for (int i = 0; i < N; ++i) if (S[i] == '0') ++zcnt;
int zcur = 0, ocur = zcnt;
for (int i = 0; i < N; ++i) {
if (S[i] == '0') t[i] = zcur++;
else t[i] = ocur++;
}
int cur = 0;
string ans;
for (int i = 0; i < N; ++i) {
ans += S[cur];
cur = t[cur];
}
reverse(ans.begin(), ans.end());
string tans = ans; tans += ans;
auto sfx = getSuffixArray(tans);
string tmp;
for (auto i: sfx) if (i < N) tmp += tans[i + N - 1];
if (tmp != S) cout << -1;
else cout << ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
항상 풀 때는 어렵지만, 풀고 나면 쉽게 느껴지는 것 같습니다…