[C++ 백준 풀이] 1701번 : Cubeditor / 16172번 : 나는 친구가 적다 (Large) / 1786번 : 찾기 (KMP)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1701번 : 'Cubeditor' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

1701번 : Cubeditor

 

주어진 문자열에서 두 번 이상 나오는 부분 문자열이 있을 때, 이들 중 가장 긴 길이를 출력하는 문제입니다. (물론 존재하지 않는 경우 답은 0이 됨)

 

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

 

위의 포스트에서 이미 KMP 알고리즘의 원리에 대해 다룬 적이 있고, 여기에서 Pi 벡터에 가장 긴 접두사 = 접미사의 길이를 저장하는 Fail 함수에 대해 구현한 적이 있으므로 이를 활용해보도록 하겠습니다.

(함수의 작동 원리에 대한 내용은 포스트를 참고해주세요.)

 

 

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

vector<int> Fail(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() {
    string Str;
    cin >> Str;
    int Max = 0;
    for(int i=0; i<Str.length(); i++) {
        vector<int> Pi = Fail(Str.substr(i, Str.length()-i));
        for(int j=0; j<Str.length()-i; j++)
            if(Pi[j] > Max) Max = Pi[j];
    }
    cout << Max;
}

 

우선 최대한 KMP 알고리즘의 기본 형태를 살리기 위해 함수를 그대로 두고 구현하였습니다.

Fail 함수가 작동하면 Pi 벡터에는 Pattern[0] ~ Pattern[i]로 구성된 문자열에서의 접두사 = 접미사인 최대 길이를 구하게 됩니다.

문제에서 요구한 것은 문자열 중간에 등장하는 일치 문자열의 길이 역시 해당되므로, 여기서는 어쩔 수 없이 시작 부분을 반복문으로 나누어 실행해주어야 합니다.

따라서 Str.length()만큼 반복을 수행하고, 이 과정에서 문자열을 분리하여 Fail 함수에 대입하기 위해 substr 함수를 사용하였습니다.

Str.substr(a, b)는 Str 문자열의 a번째 index에서부터 길이 b만큼의 문자열을 분리한 새로운 sub 문자열을 말합니다.

나머지 부분은 기존의 KMP 알고리즘의 Fail 함수 구현과 같으므로 설명은 생략하겠습니다.

 

 

 

위의 풀이 코드를 제출하면 88ms의 시간을 거쳐 모든 테스트케이스를 통과할 수 있습니다.

 

 

16172번 : 나는 친구가 적다 (Large)

 

문자열에 숫자가 섞여있을 때, 이를 배제하고 생각했을 때 부분 문자열이 포함되어 있는지 그 여부를 확인하는 문제입니다.

문자열에서 숫자를 제외하는 과정만 빼면 나머지는 KMP 알고리즘을 그대로 사용하기만 하면 되는 문제입니다.

 

 

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

vector<int> Fail(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;
}

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

int main() {
    string rawStr, Str, Pattern;
    cin >> rawStr >> Pattern;
    for(int i=0; i<rawStr.length(); i++)
        if(!(rawStr[i] >= '0' && rawStr[i] <= '9')) Str += rawStr[i];
    vector<int> Pos = KMP(Str, Pattern);
    cout << !Pos.empty();
}

 

C++에서는 Str += rawStr[i]와 같은 표현으로도 문자열 뒤에 문자를 붙일 수 있으므로 이를 활용하였습니다.

나머지는 일반적인 KMP 알고리즘의 구현과 같습니다.

 

 

 

풀이를 제출해보면 짧은 시간 안에 모든 테스트케이스를 통과하여 정답으로 인정받음을 확인할 수 있습니다.

 

 

1786번 : 찾기

 

문제 형식 자체는 아주 간결한 문제입니다.

마찬가지로 KMP를 사용하여 제한 시간 안에 돌아가는 문자열 탐색 알고리즘을 구현해야 하고, 문자열에 공백이 포함되어 이를 포함하여 입력받아야 합니다.

역시 KMP를 구현하여 똑같이 풀이해보겠습니다.

 

 

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

vector<int> Fail(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;
}

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

int main() {
    string Str, Pattern;
    getline(cin, Str);
    getline(cin, Pattern);
    vector<int> Pos = KMP(Str, Pattern);
    cout << Pos.size() << "\n";
    for(int i=0; i<Pos.size(); i++) cout << Pos[i]+1 << " ";
}

 

기존에 KMP 알고리즘을 정리한 포스트에서 거의 비슷한 코드를 다루었기에 쉽게 풀이가 가능합니다.

(풀이 자체가 일반화 된 코드를 작성해두었기 때문에, 마찬가지로 코드를 작성하는데에 오랜 시간이 걸리지 않았습니다.)

핵심은 KMP 함수에서 Str[i] = Pattern[j]인 상황에서, Pattern의 일치를 끝까지 확인한 경우 Pos 벡터에 i-j 즉 문자열이 시작하는 위치를 push_back 해주는 부분입니다.

이를 벡터에 저장하여 그대로 Pos 벡터를 리턴해주면, 메인 함수에서 이를 출력해줄 수 있습니다. (또는 발견 즉시 출력하도록 구현해도 됩니다.)

 

 

 

문제 자체가 상당히 비슷한 유형인데 Platinum V 난이도가 부여된 것을 보면 위의 두 문제의 난이도 배정이 조금 낮게 된 것 같습니다. (KMP 태그 문제들 중에서 유일하게 Gold 티어인 문제들임)

다음 포스트에서도 이어서 KMP 알고리즘 관련 문제들을 풀이해보도록 하겠습니다.