[백준] 11585번 속타는 저녁 메뉴

문제: 11585번 속타는 저녁 메뉴

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; // 문자열 s 와 p 의 길이
	cin >> n;
	string P = ""; // 패턴
	string S = "";

	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		P += c; // 연결, 공백 문자 없애기
	}
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		S += c;
	}

	// 입력된 문자열이 IWANTMEAT 이었을 때 얘를 제곱하면 IWANTMEATIWANTMEAT 이 된다.
	// 근데 위 문자열 전체에 KMP 를 수행하면 문제가 발생한다.
	// 그냥 하면 IWANTMEAT 를 두 번 확인할 수 있기 때문에 마지막 문자를 빼줘야한다..
	string doubleS = S + S;
	doubleS = doubleS.substr(0, doubleS.size() - 1);

	// KMP 사용하여 패턴이 몇 번 등장하는지 계산
	// pi 배열 먼저 구하기(패턴의 실패 함수)
	vector<int> pi(n + 1); // LPS 배열을 오른쪽으로 한 칸 민 것과 같으므로 n+1 만큼 크기 잡아주기
	int i = 1;
	int j = 0;
	while (i < n) {
		if (P[i] == P[j]) {
			i++;
			j++;
			pi[i] = j;
		}
		else if (j == 0) {
			i++;
			pi[i] = j;
		}
		else {
			j = pi[j]; // 저장해둔 곳으로 점프
		}
	}
	// 이제 doubleS 랑 P 비교 해서 패턴 개수 찾기
	int cnt = 0;
	i = 0;
	j = 0;
	
	while (i < doubleS.size()) {
		if (doubleS[i] == P[j]) {
			i++;
			j++;

			// 패턴 찾았으면 cnt 값 +1 해주고 점프
			if (j == n) {
				cnt++;
				j = pi[j];
			}
		}
		else if (j == 0) {
			i++;
		}
		else {
			j = pi[j];
		}
	}

	// 기약 분수 계산
	// 두 수의 최대공배수를 구해준 다음
	// 그 값으로 각 수를 나눠주고 출력..
	int gcd = 1;
	for (int i = 1; i <= n; i++) {
		if ((cnt % i == 0) && (n % i == 0)) {
			gcd = i;
		}
	}
	cout << (cnt / gcd) << "/" << (n / gcd) << "\n";


	return 0;
}

 

이 문제의 핵심은 주어진 문자열이 원판에 있기 때문에 원형 문자열이다. 즉 이 문제를 해결하기 위해서는 입력 받은 문자열을 제곱해 준 후 맨 마지막 글자만 떼준 다음 KMP 를 돌리면 되는 것이었다.

 

 

 

참고자료:

문제)

https://chatgpt.com/share/674c4b7d-8fc8-8003-aec5-21f3ee12a201

ChatGPT - 문자열 회전 처리

[BOJ] 백준 11585번 속타는 저녁 메뉴 (Java)

[BOJ] 백준 11585번 속타는 저녁 메뉴 (Java)

백준 11585 속타는 저녁 메뉴 Kotlin (kmp)

백준 11585 속타는 저녁 메뉴 Kotlin (kmp)

 

최소공배수)

[1934] 최소공배수 - C++ : 네이버 블로그

[1934] 최소공배수 - C++