Hashing

백준 21162번 뒤집기 K 문제풀이

[21162 뒤집기 K] https://www.acmicpc.net/problem/21162 .
해시를 이용해 접두어가 같은 부분을 빠르게 찾아내자!

신촌 ICPC 알고리즘 캠프를 이번 방학에 신청했다.
강사님이 필수과제로 내준 문제이고 솔직히 풀이를 안들었으면 못풀었을 것같다.
jhnah917님이 만드신 문제이고 풀이도 거의 비슷하게 따라 풀었다.
좋은 문제같아서 배운 내용을 정리할겸 포스팅해보려고 한다.

문제상황 파악하기.

뒤집어서 생기는 배열은 총 n-1개가 생긴다.(0~1사이, 1~2사이 …. n-2~n-1사이)
그렇다면 직접 배열을 만들면 최대 200000*200000의 공간이 필요해서 메모리가 부족할 것이다.
배열을 하나하나 만들지 않고 배열을 표현해야한다.
여기서는 cyclic shift 형태를 이용하여 거꾸로 된 배열을 2개 붙여서 이를 해결했다.
그리고 나서는 2개 이어붙여서 생긴 그 배열을 이용하여 거기서 제일 사전순으로 작은걸 찾아야한다.

해시 구현

코드는 대부분 jhnah917님이 구현하신 것을 참고했다.
누적합느낌으로 해시를 만든다.
그리고 사이의 해시값을 구할 때는 그 전의 것부터 빼야하니까 1부터 구현하는게 편하다.

const int MOD = 1000000007;
template<ll P, ll M> struct Hashing{
    vector<ll> H, B;
    void build(const vector<ll> &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])%M; //누적합 느낌으로
        }
        for(int i=1;i<=S.size();i++){
            B[i] = (B[i-1]*P)%M;
        }
    }
    ll get(int s, int e){
        ll res= (H[e]-H[s-1]*B[e-s+1])%M;
        return res >= 0 ? res : res+M;
    }
};

아이디어 얻기.

거꾸로 된 배열을 붙여서 만들 배열을 보면 1~n이 시작점인 부분만 보면된다.
그러면 어느 시작점이 사전순으로 젤 작은지를 판단해야하고 문제는 K번째를 구하는 것이므로 정렬을 해야한다.
정렬하는데에는 NlogN만큼 걸리니까 이 문제를 시간안에 해결하려면 사전순으로 더 작은지 판단하는 과정을 logN만에 해야한다.
여기서 이분탐색의 아이디어를 떠올릴 수 있다.
그리고 이분 탐색 과정에서 prefix를 비교하는데 이도 오래걸리면 안된다.
따라서 해시를 이용하여 미리 배열의 해시 값들을 저장해두고 해시 값이 달라지는 시작점을 찾아서 비교를 해야한다.

주의할 점

해시를 할때 너무 작은 M으로 나누면 안된다.
해시 충돌이 일어나기 때문이다.(해시충돌 확률은 1/M) 나는 적당히 큰 소수 P를 616327, M을 1000000007로 설정했다.
이분 탐색과정에서 Off-by-One error를 조심하자..
나는 저것때문에 2시간 가까이 고전했다…ㅠㅠ
이분탐색은 넘 어렵다.~~~

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MOD = 1000000007;
template<ll P, ll M> struct Hashing{
    vector<ll> H, B;
    void build(const vector<ll> &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])%M; //누적합 느낌으로
        }
        for(int i=1;i<=S.size();i++){
            B[i] = (B[i-1]*P)%M;
        }
    }
    ll get(int s, int e){
        ll res= (H[e]-H[s-1]*B[e-s+1])%M;
        return res >= 0 ? res : res+M;
    }
};

Hashing<616327, MOD> ht;
int n, k;
vector<ll> arr;

bool compare(int n1, int n2){   //접두어가 처음으로 다른 부분 이분탐색으로 찾기
    int l = -1 , r = n-1;
    while (l+1<r) {
        int mid = (l+r)>>1;
        int v1 = ht.get(n1, n1+mid);
        int v2 = ht.get(n2, n2+mid);
        if(v1==v2) l = mid;
        else r = mid;
    }
    if(l==n-1) return false;    //모두다 같음
    return arr[n1+r] < arr[n2+r];   //처음으로 다른부분 비교
}

int main(){
    fast_io;
    cin >> n >> k;
    arr = vector<ll> (n);
    for(int i=0;i<n;i++) cin >> arr[i];
    reverse(arr.begin(), arr.end());
    for(int i=0;i<n;i++) arr.push_back(arr[i]); //거꾸로 된거 2개 이어붙임
    
    ht.build(arr);
    vector<int> idxs(n-1);
    for(int i=0;i<n-1;i++) idxs[i]= i+1;    // i번째 부터 n-1개
    // compare(2, 6);
    stable_sort(idxs.begin(), idxs.end(), compare);
    for(int i=0;i<n;i++){
        cout << arr[idxs[k-1]+i] << ' ' ;
    }
}

Hashing

백준 21162번 뒤집기 K 문제풀이

문제상황 파악하기.

해시 구현

아이디어 얻기.

주의할 점

실제 코드

Leave a comment

2024

2023

2022