[C++ 백준 풀이] 11585번 : 속타는 저녁 메뉴 / 12104번 : 순환 순열 / 16570번 : 앞뒤가 맞는 수열

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11585번 : '속타는 저녁 메뉴', 12104번 : '순환 순열', 16570번 : '앞뒤가 맞는 수열'의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

11585번 : 속타는 저녁 메뉴

 

룰렛을 돌려서 원래 모양과 같아지는 배열이 몇 가지인지 그 비중을 출력하는 문제입니다.

문제만 읽어도 한 눈에 KMP 알고리즘을 사용하는 문제라는 것을 깨달을 수 있는 쉬운 유형의 문제입니다.

 

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

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

int GCD(int X, int Y) {
    while(Y > 0) {
        int R = X%Y;
        X = Y;
        Y = R;
    }
    return X;
}

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 KMP(string Str, string Pattern) {
    int Count = 0;
    vector<int> Pi = GetPi(Pattern);
    for(int i=0, j=0; i<Str.length()-1; i++) {
        while(j>0 && Str[i] != Pattern[j]) j = Pi[j-1];
        if(Str[i] == Pattern[j]) {
            if(j == Pattern.length()-1) {
                j = Pi[j];
                Count++;
            }
            else j++;
        }
    }
    return Count;
}

int main() {
    int N;
    cin >> N;
    string A, B;
    char C;
    for(int i=0; i<N; i++) {
        cin >> C;
        A += C;
    }
    for(int i=0; i<N; i++) {
        cin >> C;
        B += C;
    }
    int Case = KMP(A+A, B);
    int Gcd = GCD(N, Case);
    cout << Case/Gcd << "/" << N/Gcd;
}

 

간단한 KMP 문제이므로 전체적인 풀이는 어렵지 않습니다.

마지막에 기약분수를 출력하는 과정에서, 두 수의 GCD를 빠르게 구하면 좋기 때문에 유클리드 호제법을 응용해준 코드입니다.

 

 

 

 

12104번 : 순환 순열

 

바이너리 문자열 2개에 대해서, B의 순환 순열과 A의 XOR 연산으로 0이 나오는 순환 순열의 수를 구하는 문제입니다.

이 문제 역시 KMP 알고리즘을 몰랐다면 TLE에 걸리지 않고 푸는 것이 불가능했겠지만, 문자열로의 치환을 통해 풀이가 가능합니다.

 

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

#include <iostream>
#include <vector>
#include <string>
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 KMP(string Str, string Pattern) {
    int Count = 0;
    vector<int> Pi = GetPi(Pattern);
    for(int i=0, j=0; i<Str.length()-1; i++) {
        while(j>0 && Str[i] != Pattern[j]) j = Pi[j-1];
        if(Str[i] == Pattern[j]) {
            if(j == Pattern.length()-1) {
                j = Pi[j];
                Count++;
            }
            else j++;
        }
    }
    return Count;
}

int main() {
    string A, B;
    cin >> A >> B;
    cout << KMP(A+A, B);
}

 

두 수를 XOR하여 0이 나온다는 뜻은 두 수의 모든 자릿수의 수를 비교했을 때 모두 같았다는 뜻이 됩니다.

즉, 수를 회전하면서 두 수가 같은 경우의 수가 몇 가지인지 세면 되므로, KMP 알고리즘을 위와 같이 활용할 수 있습니다.

 

그리고 주의해야할 점은 KMP 함수에 A+A 문자열을 Str로 대입하였으므로, 모든 자리에 대해 비교해주면 A 문자열에 대한 비교는 2번 일어납니다. (처음에 한 번, 마지막에 한 번)

따라서 반복문의 시작을 i=1로 부여하던가, 또는 i<Str.length()-1로 조건을 두어야 Count가 잘못되는 것을 막을 수 있습니다.

 

 

 

 

16570번 : 앞뒤가 맞는 수열

 

수열의 앞 부분을 일부 잘라서 만들어진 새로운 순열이 가질 수 있는 최대 공통 접두사와 접미사의 길이를 구하는 문제입니다.

만들 수 있는 방법의 수 역시 출력해야 하므로, 그냥 보기에는 생각보다 고려해야하는 변수가 많은 문제입니다.

하지만 KMP 알고리즘의 Pi 배열을 만드는 과정을 생각해보면 간단하게 해결할 수 있습니다.

 

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> GetPi(vector<int> &Pattern) {
    vector<int> Pi(Pattern.size());
    for(int i=1, j=0; i<Pattern.size(); 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, MAX = 0, MAXCnt = 0;
    scanf("%d", &N);
    vector<int> Seq(N);
    for(int i=0; i<N; i++) scanf("%d", &Seq[i]);
    reverse(Seq.begin(), Seq.end());
    vector<int> Pi = GetPi(Seq);
    for(int i=0; i<N; i++)
        if(Pi[i] > MAX) MAX = Pi[i];
    for(int i=0; i<N; i++)
        if(Pi[i] == MAX) MAXCnt++;
    if(MAX != 0) printf("%d %d", MAX, MAXCnt);
    else printf("-1");
}

 

Pi 배열은 앞에서부터 선택한 부분 문자열에 대한 공통 접두사, 접미사의 길이를 구하여 저장하므로, 배열을 반대로 뒤집어서 Pi 배열을 구하는 트릭을 사용해줍니다.

그렇게 된다면 한 번의 GetPi 함수의 호출로 모든 원하는 값들을 구할 수 있습니다.

반환된 벡터에서 MAX 값을 찾고, 이 MAX 값을 가지는 Pi[i] 값이 몇 개인지를 구하여 답으로 출력해주면 됩니다.

만약 MAX가 그대로 0이라면 방법이 없는 것이므로 -1을 출력해줍니다.