백준 11585번 속타는 저녁 메뉴

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

환형문자열에서 부분문자열이 몇 번 일치하는지 구하는 문제이므로 Algospot JAEHASAFE(http://jaimemin.tistory.com/599)의 문제와 상당히 유사한 문제였습니다.

환형문자열 유형의 문제들은 주어진 문자열을 2배 즉, 한번 더 이어붙인 상태로 KMP 알고리즘을 수행하는 것이 핵심이였습니다.

JAEHASAFE 문제와 달리 몇 번 일치하는지가 중요하므로 return kmpSearch2(doubleOriginal, target)[0]; 대신 return kmpSearch2(doubleOriginal, target).size();를 하여 일치한 횟수를 반환해주는 것이 중요했고 또 분수를 약분해야했기 때문에 유클리드 호제법을 이용하여 기약분수로 만들어줘야했습니다.

그리고, shifts 함수를 호출할 떄 반시계 방향으로 탐색할 경우 매개변수로 original, target 순으로 전달하지만 시계 방향으로 탐색할 경우 그 반대인 target, orignal 순으로 전달합니다.

마지막으로, original = target인 경우 original을 두배 하였을 경우 두번 일치한다고 여깁니다.

따라서, original을 두배한 상태에서 마지막 인덱스를 제외하고 찾아봐야 AC를 받을 수 있는 문제였습니다.(그냥 2배 할 경우 47% 정도에서 오답처리가 됩니다!)

#include <iostream>

#include <string>

#include <vector>

using namespace std;

 

//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이면 doubleOriginal에서 다 찾다보면 두 번 찾게 되므로 doubleOriginal의 마지막 인덱스는 패스

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

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

}

 

//유클리드 호제법

int GCD(int a, int b)

{

        if (a < b)

                 swap(a, b);

        while (b != 0)

        {

                 int temp = a % b;

                 a = b;

                 b = temp;

        }

        return a;

}

 

int main(void)

{

        int N;

        cin >> N;

 

        string target, original;

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

        {

                 char temp;

                 cin >> temp;

                 target += temp;

        }

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

        {

                 char temp;

                 cin >> temp;

                 original += temp;

        }

 

        int result = shifts(target, original); //시계 방향이므로 매개변수를 거꾸로

 

        int divider = GCD(N, result);

 

        cout << result / divider << "/" << N / divider << endl; //약분한 결과

        return 0;

}

개발환경:Visual Studio 2017

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

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