백준 10266번 시계 사진들

문제 링크입니다: https://www.acmicpc.net/problem/10266

백준 11585번 속타는 저녁 메뉴(http://jaimemin.tistory.com/633)처럼 환형문자열에서 부분 문자열이 일치하는 경우가 있는지 확인하는 문제였습니다.

숫자가 360,000까지 등장할 수 있기 때문에 길이가 360,000인 배열처럼 문자열(모두 0으로)을 생성하고 입력받는 숫자의 인덱스에 해당하는 부분만 1로 바꿔서 KMP 알고리즘을 적용하면 되는 문제였습니다!

#include <iostream>

#include <string>

#include <vector>

using namespace std;

 

const int MAX = 360000 + 1;

 

//N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]를 계산

//pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이

vector<int> getPartialMatch(const string &N)

{

        int M = N.size();

        vector<int> pi(M, 0);

        //KMP로 자기 자신을 찾는다

        //N을 N에서 찾는다

        //begin==0이면 자기 자신을 찾아버리니까 안됨!

        int begin = 1, matched = 0;

        //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다

        while (begin + matched < M)

        {

                 if (N[begin + matched] == N[matched])

                 {

                         matched++;

                         pi[begin + matched - 1] = matched;

                 }

                 else

                 {

                         if (matched == 0)

                                 begin++;

                         else

                         {

                                 begin += matched - pi[matched - 1];

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return pi;

}

 

//KMP 구현

vector<int> kmpSearch2(const string &H, const string &N)

{

        int n = H.size(), m = N.size();

        vector<int> result;

        vector<int> pi = getPartialMatch(N);

 

        //현재 대응된 글자의 수

        int matched = 0;

        //짚더미의 각 글자를 순회

        for (int i = 0; i < n; i++)

        {

                 //matched번 글자와 짚더미의 해당 글자가 불일치하는 경우

                 //현재 대응된 글자의 수를 pi[matched-1]로 줄인다

                 while (matched > 0 && H[i] != N[matched])

                         matched = pi[matched - 1];

                 //글자가 대응되는 경우

                 if (H[i] == N[matched])

                 {

                         matched++;

                         if (matched == m)

                         {

                                 result.push_back(i - m + 1);

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return result;

}

 

//환형 문자열은 original 문자열을 이어붙여서 부분문자열 찾는 방식

int shifts(string &original, const string &target)

{

        //original = target이면 doubleOrginal에서 다 찾다보면 두 번 찾게 되므로 doubleOriginal의 마지막 idx는 패스

        string doubleOriginal = original + original.substr(0, original.size() - 1);

        return kmpSearch2(doubleOriginal, target).size();

}

 

int main(void)

{

        int n;

        cin >> n;

 

        string s1, s2;

 

        //길이가 MAX인 string 두개 생성(모두 0으로 초기화)

        for (int i = 0; i < MAX; i++)

        {

                 s1 += '0';

                 s2 += '0';

        }

       

        //입력받은 인덱스는 1로 변경

        for (int i = 0; i < n; i++)

        {

                 int num;

                 cin >> num;

 

                 s1[num] = '1';

        }

 

        for (int i = 0; i < n; i++)

        {

                 int num;

                 cin >> num;

 

                 s2[num] = '1';

        }

 

        if (shifts(s1, s2) == 0)

                 cout << "impossible" << endl;

        else

                 cout << "possible" << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략