[PS] 백준 #10266 시계 사진들 문제풀이

본 문제는 https://jaimemin.tistory.com/702 을 참고하여 해결하였습니다.

[ 문제 풀이 ]

• Problem : 백준 #10266
• 구분 : 문자열, KMP
• 난이도 : Platinum 5
• 풀이 방법 :
  • 처음에는 시계 바늘의 간격을 돌려서 측정해야하나 생각했는데, 입력값이 오름차순으로 주어지는 것도 아니어서 정렬이 필요하고, 환형으로 돌려가면서 맞는지 체크하려면 간격의 순서를 계속 바꿔가면서 체크해야 되는데 너무 오버헤드가 큰것 같아서 다른 방법을 구상했습니다.
  • 구상하다가 도저히 방법을 모르겠어서 위에 있는 블로그를 참고하였습니다.
    
    
  • 환형 문자열은 처음부터 문자열을 두배로 늘린 곳까지 체크해서 겹치는 부분이 있는지 확인해야 합니다. 위에서 시계는 0부터 360000미만을 가리키고 있는 n개의 바늘로 구성되어 있기 때문에 이는 길이가 360000인 문자열에서 시계 바늘이 가리키는 해당 index 부분만이 달라지는 문자열로 취급할 수 있습니다.
  • 따라서, 주어지는 n개의 바늘 위치 부분만 문자 1로 넣어주고 나머지는 0으로 이루어진 문자열 두 개를 생성하고 KMP로 두 문자에 같은 부분이 존재하는지 검사하면 됩니다.
  • 시계는 360도 방향까지 돌려서 체크해 봐야 같은 모양이 나오는지 판단할 수 있으므로 문자열 하나를 두배로 늘리고 하나는 partion-match 배열을 구해 KMP를 돌려주시면 됩니다.
  • 시간 복잡도는 O(m-n)입니다. (m: 비교 대상 문자열 길이, n: 비교할 패턴 문자열 길이)

[ 🤟🏻 Code from ss-won ]

#include <iostream>
#include <string>
#define MAX 360000
using namespace std;
int n, id;
string a, b;
int pi[MAX];

void getpi(string a){
    int j = 0;
    for(int i=1;i<MAX;i++){
        while(j != 0 && a[i] != a[j]){
            j = pi[j-1];
        }
        if(a[i] == a[j]){
            pi[i] = ++j;
        }
    }
}

bool kmp(string a, string b){
    int j = 0;
    for(int i=0;i<(int)b.length();i++){
        while(j != 0 && b[i] != a[j])
            j = pi[j-1];
        if(a[j] == b[i]){
            if(j == MAX-1)
                return true;
            else
                j++;
        }
    }
    return false;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<MAX;i++){
        a += '0';
        b += '0';
    }
    for(int i=0;i<n;i++){
        cin >> id;
        a[id] = '1';
    }
    for(int i=0;i<n;i++){
        cin >> id;
        b[id] = '1';
    }
    getpi(a);
    (kmp(a, b+b)) ? cout << "possible" : cout << "impossible";
}