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

이성훈·2022년 11월 2일
CKMPbaekjoon문자열문자열 회전속타는 저녁 메뉴
0

백준(Baekjoon online judge)

목록 보기
142/177
post-custom-banner

문제

수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원형 룰렛으로 메뉴를 선택하는 방법은 매우 독특한데, 원형 룰렛을 돌린 뒤 12시부터 시계방향으로 읽어서 나오는 모양으로 저녁 메뉴를 결정한다. 원형 룰렛에는 정확히 N개로 나누어진 칸이 존재하고, 각 칸에는 알파벳 대문자 하나가 써져있다. 또한 원형 룰렛의 12시 방향에 존재하는 화살표는 칸 사이에 걸치는 일이 없이 항상 하나의 특정한 칸을 가리키게 되며, 원형 룰렛을 돌렸을 때, N개의 칸이 12시에 존재하게 될 확률은 모두 같다.

오늘도 저녁 메뉴를 고르지 못한 수원이와 친구들은 고기를 먹자는 수원이의 의견을 반대하여 결국 원형 룰렛을 돌리게 되었다. 원형 룰렛을 돌려 수원이가 오늘 고기를 먹게 될 확률을 계산하는 프로그램을 작성하자.

입력

첫 번째 줄에는 원형 룰렛의 칸 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 두 번째 줄에는 저녁 메뉴로 고기를 선택하게 되는 원형 룰렛의 모양이 12시 방향부터 시계방향으로 공백을 구분으로 한 글자씩 N개 주어진다. 세 번째 줄에는 현재의 원형 룰렛 모양이 12시 방향으로부터 시계방향으로 공백을 구분으로 한 글자씩 N개 주어진다.

출력

원형 룰렛을 돌렸을 때 오늘 저녁으로 고기를 선택하게 되는 확률을 기약분수 형태로 출력한다. 기약분수란 분자와 분모가 더 이상 약분이 안 되는 형태를 의미한다. 만약 룰렛이 어떤 곳에 멈춰도 고기를 먹을 수 있다면 1/1 을 출력한다. 원형 룰렛을 돌려 고기를 먹을 수 있는 경우의 수는 적어도 한 가지 이상 있기 때문에 분자가 0이 되는 경우는 없다.

https://www.acmicpc.net/problem/11585

풀이

KMP알고리즘 연습문제이다. 다만 문자열 회전 에대한 테크닉이 하나 필요하다!!
어떤 문자열 S를 회전시킨 문자열 S'들중 S와 같은것의 갯수를 찾는 방법에대한 문제다.
이 문제를 문자열S의 문자를 하나씩 전부 옮겨서 문제를 처리하면 TLE가 난다.
해결법은 같은 문자열 S를 두번 겹치고나서 그중에서 S의 갯수를 찾는것이다.
예로들어 문자열 S = "abcd" 이면
S + S = "abcdabcd" 이것은 문자열을 한칸씩 회전한 결과를 모두 포함하는 문자열이된다.
여기에 찾고자하는 문자열이 abc라고 보면 아래그림과 같다.
그럼 이 2개가 실제로 문자열을 회전했을때 찾을 수 있는 횟수인지 확인해보자.
이렇게 4가지 경우가나오고 그중에 2케이스가 P를 찾은 총 횟수이다.

따라서 문자열을 직접 회전시키며 새로운 string을 생성하지말고, 이렇게 본 문자열을 두번더한것에서부터 P를 찾도록 코드를 짜면된다.

하지만 여기서 중요한점이있다.
본문자열 S == 찾는문자열P 인경우는 어떨까?
두 문자열이 같으면 총 1번찾을 수 있는경우가 2번으로 +1 되는것을 알 수 있다.
이를 해결하기 위해서는 S + S 한뒤 맨뒤문자 하나를 삭제하면 된다. 그러면 회전의결과로 생각한 문자열 S + S에서 찾고자하는 문자열 S가 한번더 찾아질 염려는 없다.
결국 이는 S를 회전시킨 문자열들의 집합 S'에서 문자열 P와 같은것의 갯수를 찾을때 S == P일경우를 고려하여 S + S - 1(char)에서 P를 탐색하는것이다.

이 내용대로 KMP알고리즘을 적용시켜보자.

  1. 입력받는 부분
    위에서 설명한 문자열 S를 string input으로 받았다.
    그리고 line 101~102에서 input + input - 1(char)로 input을 재설정 해주고있다.



  2. 실패함수 : 실패테이블을 리턴
    찾고자하는 문자열을 전달받아 실패테이블을 만든다.



  3. KMP검색함수 : 본문자열input에서 찾는문자열pattern이 일치하는 갯수를 리턴
    line131에서 문자열pattern을 찾은경우 res + 1해주고,
    line132에서 이어서 재탐색이 가능하도록 j 값을 F[j]. 즉 j를 되돌릴건데(j포인터를 좌로이동) 건너띌수있는 만큼 건너띄도록 실패테이블을 이용하는 모습이다.



  4. 프로그램의 메인 로직

    line 145 : 실패테이블을만든다.
    line 146 : KMP로 일치하는 갯수를 찾는다.
    line 147~150 : 기약분수꼴로 나타내기위해 N과 res를 조정한다.




아마 이문제는 맨위에서 설명한 문자열 S를 회전시킨 결과문자열의 집합 S'에서 S와 같은길이의 문자열 P를 찾을때의 테크닉 하나를
알고있으면 풀 수 있는 문제다.(KMP알고리즘 또한 알고있다면.)

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
#define MAX 1000000
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
//_UG std::max; //_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }


int N;
string pattern, input;
void init();
void func();

void init() {
	sc("%d", &N);
	char junk;
	rep(i, N) { //패턴입력
		sc("%c%c", &junk, &junk);
		pattern += junk;
	}

	rep(i, N) {
		sc("%c%c", &junk, &junk);
		input += junk;
	}

	input += input;
	input.pop_back();
}
vi makeFailureTable(string pattern) {
	int lenP = pattern.length();
	vi F(lenP, 0); //lenP만큼 0으로 초기화

	int j = 0;
	rrep(i, 1, N) {
		while (j > 0 && pattern[i] != pattern[j])
			j = F[j - 1];
		if (pattern[i] == pattern[j])
			F[i] = ++j;
	}

	rt F;
}

int KMP(string str, string pattern, vi F) {
	int lenS = str.length();
	int lenP = pattern.length();

	int res = 0;

	int j = 0;
	rrep(i, 0, lenS) {
		while (j > 0 && str[i] != pattern[j])
			j = F[j - 1];
		if (str[i] == pattern[j]) {
			if (j == lenP - 1){
				res++;
				j = F[j];
			}
			else
				j++;
		}
	}

	rt res;
}

//프로그램 메인 로직
void func() {
	vi F = makeFailureTable(pattern);
	int res = KMP(input, pattern, F);
	while (res != 1 && N % res == 0) {
		N /= res;
		res /= res;
	}

	pr("%d/%d", res, N);
}

int main(void) {
	init();
	func();

	rt 0;
}
profile
이성훈
I will be a socially developer
이전 포스트

[백준 C++] 11097 도시 계획

다음 포스트

[백준 C++] 5052 전화번호 목록

post-custom-banner

0개의 댓글