백준21162 뒤집기 K

작성일 | In

문제 링크

  • http://icpc.me/21162

사용 알고리즘

  • 해싱

시간복잡도

  • $O(N \log^2 N)$

풀이

오랜만에 BOJ에 문제를 올렸습니다.

두 수열을 잘 쪼갠 뒤 각각 뒤집어서 붙이는 것은 무엇을 의미할까요? 앞부분과 뒷부분을 각각 X개와 N-X개로 쪼개면 수열은 $A[X], A[X-1], A[X-2], \cdots , A[1], A[N], A[N-1], \cdots , A[X+1]$이 됩니다.
입력으로 들어온 수열을 뒤집어서 생각하면, 수열을 $[1, N)$번 Cyclic Shift한 수열을 만들게 됩니다.

K-th Lexicographically Cyclic Shift를 찾는 문제가 되었습니다. 문자열(수열)의 Cyclic Shift는 문자열을 2배 늘려주면 처리하기 쉬워집니다. 그러므로 우리는 $A[2..N+1], A[3..N+2], \cdots , A[N..2N-1]$ 중 사전순 $K$번째 문자열(수열)을 찾으면 됩니다.

부분 문자열의 사전순 비교를 $T(N)$ 시간에 할 수 있다면, 만들 수 있는 모든 문자열을 나열한 뒤 $O(T(N) \cdot N \log N)$에 정렬하고 $K$번째 문자열을 출력하는 것으로 문제를 해결할 수 있습니다. 이 글에서는 문자열의 사전순 비교를 $O(\log N)$에 하는 방법을 소개합니다.

두 문자열이 완전히 같은지 확인하는 것은 해싱을 이용해 $O(1)$에 할 수 있다는 것이 잘 알려져 있습니다.
ㅇ러떤 두 문자열 $A, B$가 있을 때, $A$가 $B$보다 사전순으로 앞선다는 것은, 어떤 자연수 $X$가 있어서 $A[..X-1]$과 $B[..X-1]$이 서로 같고 $A[X]$와 $B[X]$가 다르며(처음으로 다른 위치가 $X$이며), $A[X] < B[X]$라는 것을 의미합니다. 그러므로 두 문자열이 처음으로 달라지는 위치를 파라메트릭 서치를 이용해 $O(\log N)$만에 찾고, 그 지점의 문자를 비교하면 됩니다.

두 문자열을 $O(\log N)$만에 비교할 수 있으므로 $N$개의 부분 문자열을 $O(N \log^2 N)$에 정렬할 수 있습니다.

아래 코드는 단일 해시를 사용한 코드이며, 해싱을 2-3중으로 사용하고 싶다면 다음과 같이 cmp 함수를 수정하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
constexpr int P1 = 1299709, M1 = 1'000'000'007;
constexpr int P2 = 1301021, M2 = 1'000'000'009;
constexpr int P3 = 1300333, M3 = 1'000'000'103;
Hashing<P1, M1> H1;
Hashing<P2, M2> H2;
Hashing<P3, M3> H3;

tuple<int,int,int> sub(int s, int e){
    return {H1.sub(s, e), H2.sub(s, e), H3.sub(s, e)};
}

bool cmp(int a, int b){
    int l = 0, r = N-1;
    while(l < r){
        int m = l + r + 1 >> 1;
        auto t1 = sub(a, a+m-1), t2 = sub(b, b+m-1);
        if(t1 == t2) l = m;
        else r = m - 1;
    }
    if(l == N-1) return false;
    return V[a+l] < V[b+l];
}

전체 코드

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PLL = pair<ll, ll>;

template<ll P, ll M> struct Hashing{
    vector<ll> H, B;
    void Build(const vector<int> &S){
        H.resize(S.size()+1);
        B.resize(S.size()+1);
        B[0] = 1;
        for(int i=1; i<=S.size(); i++) H[i] = (H[i-1] * P + S[i-1]) % M;
        for(int i=1; i<=S.size(); i++) B[i] = B[i-1] * P % M;
    }
    ll sub(int s, int e){
        s++; e++;
        ll res = (H[e] - H[s-1] * B[e-s+1]) % M;
        return res < 0 ? res + M : res;
    }
};

int N, K;
vector<int> V;
Hashing<524287, 998244353> H1;

bool cmp(int a, int b){
    int l = 0, r = N-1;
    while(l < r){
        int m = l + r + 1 >> 1;
        auto t1 = H1.sub(a, a+m-1), t2 = H1.sub(b, b+m-1);
        if(t1 == t2) l = m;
        else r = m - 1;
    }
    if(l == N-1) return false;
    return V[a+l] < V[b+l];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; V.reserve(N+N-1); V.resize(N);
    for(auto &i : V) cin >> i;
    reverse(all(V));
    for(int i=0; i<N-1; i++) V.push_back(V[i]);
    H1.Build(V);

    vector<int> ord(N-1);
    iota(all(ord), 1);
    stable_sort(all(ord), cmp);
    for(int i=0; i<N; i++) cout << V[ord[K-1]+i] << " ";
}