[C++] 백준 1305 번 문제 해설

문제 설명

 

백준 1305번 문제는 다음과 같다.

1305번: 광고

 

문제에 관해 간략히 해설하자면, 흔히 보는 전광판에서 글자가 돌아가며 출력될 때, 특정 순간에 전광판을 포착했을 때

전광판은 특정 문자열로 구성되어 있을 터인데,

전광판 사이즈보다 글자 수가 적다면, 특정 글자가 반복될 것이다.

 

이 때, 최소 str.length() 가 얼마인지 return 하면 되는 간단한 문제이다.......

간단한 문제라고 생각했었는데, 생각보다 복잡하였다.

 

 

풀이 시행착오

이 문제의 경우 KMP 알고리즘에서 사용되는 make_pi 로직을 찾아 사용하였다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int getPI_cyp(string& str)
{
    int len = str.length();
    int pre = 0;
    int pos = 1;
    int count = 0;

    while (pos < len)
    {
        if (str[pre] == str[pos])
        {
            ++count;
            ++pre;
            ++pos;
        }
        else
        {
            if (pre > 0 && str[pre - 1] == str[pos])
            {
                ++pos;
                continue;
            }

            pre = 0;
            count = 0;
            ++pos;
        }
    }
    return count;
}


int getPI_example(string& str)
{
    int len = str.length();
    int pre = 0;
    int pos = 1;

    vector<int> table;

    table.resize(len);

    int count = 0;

    for (; pos < len; pos++)
    {
        while (pre > 0 && str[pre] != str[pos])
        {
            pre = table[pre - 1];
        }
        if (str[pre] == str[pos])
        {
            table[pos] = ++pre;
        }
    }

    return table[len - 1];
}


int main()
{
    int len;
    string str;

    cin >> len >> str;
    //cout << len - getPI_cyp(str) << std::endl;
    cout << len - getPI_example(str);

}

위 getPI_cyp() 함수가 내가 만든 알고리즘인데,

일반적인 입력값을 넣었을 때 아래 getPI_example() 함수와의 차이점을 알 수 없었다.

그래서 랜덤 string 을 뽑는 함수를 통해 무작정 돌려보니

"NwNwNN" 라는 문자열에서 두 알고리즘 출력값의 차이점이 발생하였다.

이를 토대로 내 알고리즘이 무엇이 잘못되었나 다시 디버깅 하였다.

 

 

풀이 방법

풀이 방법을 알기 위해서는 KMP 알고리즘과 make_pi 에 관해 이해하여야 한다.

기본적으로 text 를 찾는 알고리즘이 KMP 알고리즘이고, 이 원리를 이용해서 해당 문제를 해결 할 수 있다.

KMP : 문자열 검색 알고리즘

자세한 내용은 멍멍멍님의 블로그에 상세히 나와 있다.

 

결론적으로 중복되는 접두와 접미쌍의 길이를 총 문자열 길이에서 빼면된다.

예로

aabaaa = 6 - 2 = 4

aaaaaa = 6 - 5 = 1

 

여기서, 맨 첫글자, 맨 마지막 글자는 '접두','접미' 로 남겨 두어야 한다.

aaaaaa 라고 해서 6 - 6 = 0 가 되지 않는다는 말이다.

 

 

 

풀이

"NwNwNN" 에선 접두(pre), 접미(pos) 가 1개씩 겹치므로

6 - 1 = 5 의 값이 나오는것이 정상이나, 내 알고리즘에서는 정상값이 도출되지 못 하였다. 

그에따라 인용한 make_pi 알고리즘을 돌린 함수를 분석 해 보았다.

 

우선 getPI_example 알고리즘에서 가장 중요한 부분은 아래 부분이다.

while 문을 진입하는데에 있어서 str[pre] != str[pos] 조건을 만족해야만 진입하는데,

진입한 뒤에는 table[pre - 1] 을 pre 에 대입한다.

이게 무슨 뜻이냐면,

 

NwNwNN 과 NwNwNN 을 서로 비교할 때,

pre = 3(w), pos = 5 (N)

일 때 불일치가 나타난다.

불일치가 나타났다면 여기서 pos는 유지한 채로, pre를 역행시킨다.

pre를 역행시킬 때, 불일치가 발생한 

pre 를 역행시키면서 table[pre - 1] 내에 위치한 놈들을 현재 pos 와 일치하는지 비교하는 과정을 거친다.

 

간단하면서도 실용적인 발상이다.

아마 내가 설계했다면 이런식으로는 생각하는데 상당히 오랜 기간이 걸렸을 것이다.