[BOJ 백준] 1305번 광고

문제

BOJ 1305 : https://www.acmicpc.net/problem/1305

1305번: 광고

접근

문제를 읽고 가장 먼저 떠오른 방법은 Brute-Force(완전 탐색)를 이용한 방법이었다.

하지만 Brute-Force는 O(N*M)의 시간복잡도를 가지는데, 문제에서 L(문자열 길이)의 최댓값이 백만이기 때문에 Brute-Force를 통해 구현하면 무조건 시간 초과가 날 것이다.

풀이 방법이 마땅히 떠오르지 않아 문자열과 관련된 알고리즘을 알아보다 KMP에 대해 알게 되었다.

 

KMP알고리즘이란 접두사와 접미사를 활용하여 효율적으로 문자열을 검색하는 알고리즘이다.

무려 O(N+M)의 시간복잡도로 문자열 검색을 마칠 수 있다.

KMP 알고리즘에 관해 라이 님과 안경잡이개발자 님의 블로그를 참고했다.

 

KMP 알고리즘을 활용하여 문자열의 0번째부터 차례대로 접두사와 접미사의 최대 일치 길이를 카운트해 나간 뒤 문자열의 가장 마지막까지 도달했을 때의 접두사와 접미사의 최대 일치 길이를 전체 문자열 길이에서 빼주면 된다.

예를들어 문자열 L로 '맛있는사과맛있'가 주어졌다면

맛있는사과맛있

접두사와 접미사의 최대 일치 길이는 2가 된다.

전광판은 한 문자열의 무한한 반복으로 이루어져 있음으로 마지막 문자 기준 접두사와 접미사의 최대 일치 길이만큼 문자열 L이 재출력 되었다고 볼 수 있다.

코드

// algorithm study
// BOJ_1305_광고

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int num, j = 0;
    string s;
    cin >> num >> s;
    vector<int> fail(s.size(), 0);
    for (int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j])
            j = fail[j - 1];
        if (s[i] == s[j])
            fail[i] = ++j;
    }
    cout << num - fail[num - 1];
    return 0;
}

깃 허브 주소 : https://github.com/algoribi/algorithm-study