[Baekjoon,10266] 시계 사진들

시계를 회전하여서 두 시계가 일치 가능한지 찾아야 한다. 이는 시계 바늘 간의 간격이 모두 동일하다면 같다고 생각할 수 있다. 따라서 시계 바늘이 가르키는 방향을 정렬한 후 바늘 간의 간격을 얻어 두 시계의 바늘 간격들이 같은지 확인하면 된다.
이때 시계의 바늘이 가르키는 방향이 원형으로 연결되어 있는 것을 고려해야 한다. 즉, 12시 방향을 기준으로 좌측에서 우측으로 넘어가는 간격을 유념해야 한다. 아래와 같은 입력을 생각해보자.

// input
7
1 2 3 4 5 6 7
359998 359999 0 1 2 3 4
// output
possible

두 번째 시계를 오른쪽으로 $2$만큼 회전시켜 두 시계가 일치함을 알 수 있다. 그러나 정렬을 한 후 간격을 구해 비교하기가 까다로운 것을 알 수 있다.

// after sort
1 2 3 4 5 6 7
0 1 2 3 4 359998 359999

이는 첫 번째 시계가 가르키는 방향들을 그대로 뒤에 이어서 합치면 해결할 수 있다.

1 2 3 4 5 6 7 1 2 3 4 5 6 7
0 1 2 3 4 359998 359999

// 간격 
1 1 1 1 1 (360000 - 6 = 359994) 1 1 1 1 1 1
1 1 1 1 359994 1

이와 같은 전처리 과정을 마치고 나서 $KMP$ 알고리즘을 이용하여 두 번째 시계 바늘 간격이 첫 번째 시계 바늘 간격에 존재하는지 찾으면 된다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_ANGLE=360000;

int len;

// 바늘 사이의 간격으로 계산하여 저장한다.  
void preCalc(vector<int>& H, vector<int>& N)
{
    sort(H.begin(),H.end());
    sort(N.begin(),N.end());
    for(int i=0;i<len;++i)
        H.push_back(H[i]);
    for(int i=1;i<len*2;++i)
    {
        int diff=H[i]-H[i-1];
        H[i-1]=(diff<0 ? MAX_ANGLE+diff : diff);
        if(i<len)
            N[i-1]=N[i]-N[i-1];
    }
    H.pop_back();
    N.pop_back();
}

vector<int> getPartialMatch(const vector<int>& N)
{
    int n=N.size();
    vector<int> pi(n,0);
    int matched=0;
    for(int i=1;i<n;++i)
    {
        while(matched>0 && N[i]!=N[matched])
            matched=pi[matched-1];
        if(N[i]==N[matched])
        {
            ++matched;
            pi[i]=matched;
        }
    }
    return pi;
}

// KMP알고리즘을 이용하여 바늘 간격이 동일한지 찾는다. 
bool same(const vector<int>& H, const vector<int>& N)
{
    int n=H.size(), m=N.size();
    vector<int> pi=getPartialMatch(N);
    int matched=0;
    for(int i=0;i<n;++i)
    {
        while(matched>0 && H[i]!=N[matched])
            matched=pi[matched-1];
        if(H[i]==N[matched])
        {
            ++matched;
            if(matched==m)
                return true;
        }
    }
    return false;
}

int main()
{
    cin>>len;
    vector<int> H(len), N(len);
    for(int i=0;i<len;++i)
        scanf("%d",&H[i]);
    for(int i=0;i<len;++i)
        scanf("%d",&N[i]);
    
    preCalc(H,N);
    if(same(H,N))
        cout<<"possible"<<endl;
    else
        cout<<"impossible"<<endl;
    
    return 0;
}