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

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1893번 : '시저 암호'와 4354번 : '문자열 제곱' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

1893번 : 시저 암호

 

알파벳과 찾을 문자열, 그리고 암호문이 순서대로 주어졌을 때, 주어진 알파벳 순서대로 shift한 문자열이 암호문에서 한 번만 등장하게 하는 shift 값을 출력하는 문제입니다.

알파벳 순서 자체를 정해주므로 주어진 알파벳대로 shift 해야하며, 암호문에서 2번 이상 등장하는 문자열은 배제해야 하기 때문에 고려해야 할 조건이 쉽지 않은 문제입니다.

 

 

#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() {
    int T;
    cin >> T;
    for(int t=0; t<T; t++) {
        string Alphabet, Str, Pattern;
        vector<int> Ans;
        cin >> Alphabet >> Pattern >> Str;
        for(int i=0; i<Alphabet.size(); i++) {
            vector<int> Pos = KMP(Str, Pattern);
            if(Pos.size() == 1) Ans.push_back(i);
            for(int j=0; j<Pattern.length(); j++)
                for(int k=0; k<Alphabet.length(); k++)
                    if(Pattern[j] == Alphabet[k]) {
                        Pattern[j] = Alphabet[(k+1)%Alphabet.length()];
                        break;
                    }
        }
        if(Ans.size() == 0) cout << "no solution";
        else if(Ans.size() == 1) cout << "unique: ";
        else cout << "ambiguous: ";
        for(int i=0; i<Ans.size(); i++) cout << Ans[i] << " ";
        cout << "\n";
    }
}

 

풀이 코드를 보면, 우선 각 테스트케이스에 대해 반복적으로 수행되도록 반복문을 구성하였습니다.

KMP 알고리즘을 이용해 문자열을 탐색해주고 Pos.size를 확인하여 문자열이 암호문에서 단 한 번만 등장하는지 확인합니다.

이 과정을 Alphabet의 크기만큼 반복하여 한 번 수행할 때마다 알파벳 순서대로 shift를 수행해줍니다.

각 문자에 대해 shift 이후 break를 해주어야 함에 주의해야 합니다.

나머지는 Ans에 저장된 해들을 개수에 따라 다르게 조건문을 설정하여 출력해주기만 하면 됩니다.

 

 

 

제출해보면 748ms라는 짧지 않은 시간에 CA를 받을 수 있지만, 사실 문제 자체에서 1초가 아닌 2초로 제한 시간을 두기 때문에 적절한 알고리즘을 사용했다고 볼 수 있습니다.

 

 

4354번 : 문자열 제곱

 

입력으로 주어진 문자열이 특정 부분 문자열이 반복되는 문자열이라면, 그 부분 문자열의 길이를 출력하는 문제입니다.

당연히 제한 시간 내에 일일이 탐색할 수는 없으므로 KMP 알고리즘을 응용해야 합니다.

 

 

예시로 문자열 몇 개를 놓고 풀이를 잘 생각해보면 규칙성을 발견할 수 있습니다.

L과 Pi[L-1]을 두고 생각해보면, L이 두 수의 차이로 나눠떨어지는 경우 부분 문자열의 반복으로 이루어짐을 알 수 있습니다.

따라서 이를 활용하여 풀이를 구현해주면 됩니다.

 

 

#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;
    while(1) {
        cin >> Str;
        if(Str.compare(".") == 0) break;
        vector<int> Pi = Fail(Str);
        int L = Str.length();
        if(L%(L-Pi[L-1]) == 0) cout << L/(L-Pi[L-1]) << "\n";
        else cout << "1\n";
    }
}

 

코드의 Fail 함수가 Pi 벡터를 기록하여 반환해주는 함수입니다. (KMP 알고리즘 구현을 그대로 수행함)

나누어떨어지는 경우는 그 값을 출력해주면 되고, 그렇지 않은 경우는 결국 그 문자열 전체가 1번 반복된 것으로 볼 수 있으므로 1을 출력해주면 됩니다.

 

 

 

제출해보면 짧지 않은 시간이 소요되지만 어찌되었든 정답 처리를 받을 수 있습니다.