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

본문 링크

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

vector<int> maketable(vector<int>& pattern)
{
    int patternsize = pattern.size();

    vector<int> table (patternsize,0);

    int j = 0;

    for (int i = 1 ; i < patternsize ; i++)
    {
        while (j>0 && pattern[i]!=pattern[j])
        {
            j=table[j-1];
        }
        
        if (pattern[i]==pattern[j])
        {
            table[i]=++j;
        }
    }

    return table;
}

string KMP(vector<int>&pattern , vector<int>&parent)
{
    vector<int> table = maketable(pattern);

    int patternsize = pattern.size();
    int parentsize = parent.size();

    int j = 0;

    for (int i = 0 ; i < parentsize ; i++)
    {
        while (j>0 && parent[i]!=pattern[j])
        {
            j=table[j-1];
        }

        if (parent[i]==pattern[j])
        {
            if (j==patternsize-1)
            {
                return "possible";
            }

            else
            {
                j++;
            }
        }
    }

    return "impossible";
}
int main()
{
    int N;

    cin >> N;

    vector<int> parent(MAX*2, 0);
    vector<int> pattern(MAX,0);

    for (int i = 0 ; i < N ; i ++)
    {
        int K1;
        cin >> K1;
        parent[K1]=1;
        parent[K1+MAX]=1;
    }

    for (int i = 0 ; i < N ; i ++)
    {
        int K2;
        cin >> K2;
        pattern[K2]=1;

    }

    cout << KMP(pattern , parent);

}

📌 어떻게 접근할 것인가?

정말 좋은 문제라고 생각합니다.
일단 KMP 를 사용해서 풀었습니다.

KMP 태그가 있는 문제들을 풀고있는 중이었는데 , 만약 KMP 태그가 있다는걸 몰랐으면 정말 정말 접근하기 어려운 문제라고 생각합니다.

물론 다양한 풀이법이 있겠지만 이 문제를 보고 KMP 를 사용한다고 발상하기에는 아주 까다롭다고 생각합니다. 왜냐하면 KMP 는 문자를 비교한다는 생각이 가장먼저 들기 때문입니다.

KMP 를 활용해서 문자를 넣는 것이 아니라 , 인덱스 자체를 숫자로 생각해서 입력받는 인덱스 값을 1 로 만들어 주었습니다.

다만 시계이기 때문에 parent 벡터는 두배인 720000 으로 크기를 설정했습니다. 한바퀴 돌 수 있기 때문입니다.

KMP 을 통해서 두 문자열이 일치하는지 판단하는 방법은 똑같은 문자가 일정한 인덱스의 증가량에 따라 같은지 에 대해 판별합니다.

즉 문자가 같은지에 대해서는 인덱스와 문자를 확인하므로 이는 숫자로 변경해서 생각할 수 있습니다.

특정 숫자가 일정한 변화에 일치하게 증가하는가? 로 생각할 수 있습니다.

문제에서 시계는 시계의 절대적 위치는 전혀 중요하지 않고 각 시계 초점들에 대해서 일정한 변화량이 서로 같은지 확인해야 하기 때문입니다.

따라서 특정 인덱스에 일정한 변화량 만큼 똑같은 값이 들어오는지 확인해줌으로써 KMP 를 적용할 수 있습니다.