백준 10266번: 시계 사진들 (C++)

https://www.acmicpc.net/problem/10266

10266번: 시계 사진들

---

Level: Platinum IV

Solved By: KMP

 

우선 각도들이 크기에 상관없이 랜덤 하게 주어지기 때문에 정렬을 해줄 필요가 있습니다. 시계 모양이 같다는 건 시침을 모두 두었을 때 인접한 시침마다의 각이 같다는 것을 뜻합니다. 즉, 정렬한 배열의 인접한 수들의 차를 구하여 새로운 배열을 만들면 됩니다.

vector<int> process(vector<int>& v){
    vector<int> ret;
    for(int i = 1; i < v.size(); i++){
        ret.push_back(abs(v[i] - v[i - 1]));
    }
    return ret;
}

이 함수를 통해 입력으로 주어진 두 배열이 같은지를 확인하면 끝날까요? 아닙니다.

반례를 가져와봤습니다.

input:
3
1 359998 359999
0 1 3

위 케이스를 그림을 그려보면 이루는 각도들이 같다는 것을 알 수 있습니다.

 

입력으로 주어진 밑 배열의 각도 차이 값을 구하면 {1, 2}이 나옵니다.

위 배열의 각도 차이 값을 구하면 {359997, 1}이 나옵니다. 그런데 왜 같은 모양일까요.

 

위 배열은 1, 359998, 359999에서 359998, 359999, 360001로 볼 수 있고, 이 각도 차이 값을 구하면 {1, 2}가 되기 때문입니다. 즉, 위 배열은 입력을 받으면서 원소에 입력 최댓값(360000)까지 더한 원소를 추가적으로 push를 해줘야 합니다. 그럼 각도의 모든 차이 값들을 구할 수 있습니다.

 

하지만, 여기서 질문이 생길 수 있습니다.

Q: "그럼 첫 원소에만 +360000 해준 값을 push 해주면 되지 않을까? 그래도 충분히 모든 각도 차이 값들을 구할 수 있잖아."

 

input:
3
1 2 359999
0 2 3

이런 경우도 단순히 첫 원소만 마지막 원소에 +360000하여 해결할 수 있을까요? 아닙니다.

모든 원소들에 +360000한 값들을 push 해줘야 풀리는 걸 볼 수 있죠.

위 배열 각도 차이값(모든 원소에 +360000한 값들까지)을 A, 밑 배열 각도 차이 값을 B라 해봅시다.

A: {1, 359997, 2, 1, 359997}

B: {2, 1}

각도 차이 값이 이렇게 나오기 때문에 결론적으로 B라는 수열이 A에 속해있는지 확인해봐야 합니다. 하지만, O(A's length * B's length)로 시간 초과가 날 수 있습니다. 이럴 때 쓸 수 있는 알고리즘 KMP를 통해 O(A's length + B's length)로 구현할 수 있어야 합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 360000
using namespace std;

int N;
vector<int> v1, v2, v3;

vector<int> process(vector<int>& v){
    vector<int> ret;
    for(int i = 1; i < v.size(); i++){
        ret.push_back(abs(v[i] - v[i - 1]));
    }
    return ret;
}

vector<int> getPi(vector<int> p){
    vector<int> pi(p.size(), 0);
    
    for(int i = 1, j = 0; i < p.size(); i++){
        while(j > 0 && p[i] != p[j]) j = pi[j - 1];
        if(p[i] == p[j]) pi[i] = ++j;
    }
    
    return pi;
}

bool kmp(vector<int> s, vector<int> p){
    auto pi = getPi(p);
    
    for(int i = 0, j = 0; i < s.size(); i++){
        while(j > 0 && s[i] != p[j]) j = pi[j - 1];
        if(s[i] == p[j]){
            if(j == p.size() - 1) return 1;
            else j++;
        }
    }
    return 0;
}

int main(){
    cin >> N;
    
    for(int i = 0; i < N; i++){
        int a; cin >> a; v1.push_back(a); v1.push_back(a + MAX);
    }
    
    for(int i = 0; i < N; i++){
        int a; cin >> a; v2.push_back(a);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    auto q1 = process(v1);
    auto q2 = process(v2);
    
    if(kmp(q1, q2)){
        cout << "possible";
    }
    else{
        cout << "impossible";
    }
    return 0;
}