[C++ 백준 풀이] 16900번 : 이름 정하기 / 1305번 : 광고 / 1498번 : 주기문 (KMP 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 16900번 : '이름 정하기', 1305번 : '광고', 1498번 : '주기문' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 문자열 탐색 알고리즘인 KMP 알고리즘에 대한 이해가 필요합니다.

 

[C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘)

 

KMP 알고리즘 코드와 원리 설명은 위의 링크에 정리되어 있으니, 알고리즘에 대해 모를 경우 이를 먼저 참고하시면 좋습니다.

 

 

16900번 : 이름 정하기

 

부분 문자열 S가 K번 등장하는 문자열 중 가장 짧은 것의 길이를 구하는 문제입니다.

접두사와 접미사가 같은 문자열일 경우 공통 길이만큼 겹쳐서 문자열을 짧게 만들 수 있으므로, 결국은 최대 공통 접두사, 접미사의 길이를 구해야 합니다.

이를 짧은 시간에 효율적으로 구하기 위해서는 KMP 알고리즘의 GetPi 함수를 사용하면 되므로, 이를 활용하여 풀이하면 됩니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> GetPi(string &Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main() {
    int N;
    string Str;
    cin >> Str >> N;
    vector<int> Pi = GetPi(Str);
    int L = Str.length();
    cout << ((long long)N-1)*(L-Pi[L-1])+L;
}

 

구현은 똑같이 하면 되지만, 최대 범위를 넣고 계산해보면 곱셈 부분에서 int형을 벗어나기 때문에 오버플로우에 유의해야 합니다.

자동형변환의 경우 왼쪽 방향으로 결합하면서 진행되기 때문에 저는 N에 long long 처리를 해서 출력해주었습니다.

 

 

 

위의 알고리즘대로 풀어서 제출해보면 24ms를 기록하고 정답 처리를 받을 수 있습니다.

 

 

1305번 : 광고

 

길이 N인 전광판에 광고 문자열이 주어질 때, 가능한 가장 짧은 광고의 길이를 구하는 문제입니다.

예를 들어 광고가 abcd로 그 길이가 4이고, 전광판의 길이가 6이라고 할 때, 전광판에는 abcdab가 출력됩니다.

이 경우 어떤 시점에서 전광판을 보더라도 앞의 문자열 2개와 뒤의 문자열 2개는 동일하게 됩니다.

따라서 가장 긴 접두사 = 접미사의 길이를 구해서 전광판의 길이에서 빼주면 최소 광고 길이가 됩니다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> GetPi(string &Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main() {
    int N;
    string Str;
    cin >> N >> Str;
    vector<int> Pi = GetPi(Str);
    int L = Str.length();
    cout << L-Pi[L-1];
}

 

최대 길이 접두사 = 접미사를 구하기 위해 KMP 알고리즘의 Pi 함수를 사용해줍니다.

알고리즘 자체는 일반적인 KMP 알고리즘과 동일하므로 설명은 생략하겠습니다.

 

 

 

제출해보면 40ms 시간이 소요되고 정답 처리를 받을 수 있습니다.

 

 

1498번 : 주기문

 

입력된 문자열을 0번째 index ~ i번째 index까지 선택하여 만들어지는 부분 문자열들에 대해서, 2번 이상 반복되는 문자열인 것의 길이와 반복 횟수를 출력하는 문제입니다.

 

[C++ 백준 풀이] 1893번 : 시저 암호 / 4354번 : 문자열 제곱 (KMP)

위 포스트에서 다룬 4354번 : '문자열 제곱' 문제의 아이디어를 사용하면 됩니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> GetPi(string &Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main() {
    int N;
    string Str;
    cin >> Str;
    vector<int> Pi = GetPi(Str);
    for(int i=1; i<=Str.length(); i++)
        if(i%(i-Pi[i-1]) == 0 && i/(i-Pi[i-1]) > 1)
            cout << i << " " << i/(i-Pi[i-1]) << "\n";
}

 

풀이에 대해 간략하게만 설명하자면 문자열의 길이 L과 Pi[L-1] 사이의 규칙성을 활용하여, 주기문일 경우 L이 L-Pi[L-1]로 나누어떨어지며 이 때 반복 횟수는 L/(L-Pi[L-1])이라는 특성을 이용하는 풀이입니다.