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

#11585 속타는 저녁 메뉴

난이도 : 플레 5

유형 : 문자열  / KMP

11585번: 속타는 저녁 메뉴

▸ 문제

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

 

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

주어진 룰렛판을 돌려 저녁 메뉴를 고기로 먹게되는 케이스의 확률이 얼마나 되는지 구해주면 된다. 룰렛을 일자로 펼쳐 문자열을 돌려봤을 때 발생하는 경우의 수는 총 룰렛의 크기인 N이다. 그리고 고기를 먹을 패턴이 오게 될 확률은 P이다. P는 무조건 1 또는 그 이상이다. 우리는 그 이상일 경우를 구해주면 된다. 

 

이 경우에 대해 제일 단순한 방법은 룰렛의 문자열 확장(parent*2)시켜 pattern와 몇 번 매칭되는지 확인하는 방법이다. 예를 들어, 'ABAB'의 룰렛판이 있을 때 'BABA'순서로 룰렛이 오게되면 고기를 먹는다고 해보자. 그러면 다음 표와 같이 2번 매칭되는 것을 확인할 수 있다. (0번과 N번 매칭은 중복이므로 주의하자.)

 

A	B	A	B	A	B	A	B	cnt
	B	A	B	A				1
			B	A	B	A		2

 

최대 100만이 되는 문자열을 무작정 비교할 수는 없다. 룰렛 크기를 2배로 확장시키면 200만에 기존 100만 길이가 되는 패턴을 매칭시키면 감당할 수 없는 연산 횟수를 하게 된다. 그러므로 KMP 문자열 매칭 알고리즘을 사용해서 풀이해주면 된다.

 

설계

1. 룰렛 크기를 2배 확장한 문자열(parent)과 고기를 먹게되는 문자열(pattern)을 KMP 매칭 알고리즘을 돌려준다.
   1. pattern 문자열의 부분 일치 테이블을 생성한다. int[] table = makeTable(pattern);
   2. parent의 문자열의 길이를 n1이라 할 때, for문은 0~n1-2까지 탐색해준다. (첫 문자열과 마지막 문자열 중복 방지)
   3. idx : 현재 대응되는 글자 수, i : parent의 문자열 위치
   4. idx번 글자와 parent(i)글자가 불일치할 경우, 현재 대응되는 글자의 수를 table[idx-1]로 줄인다.
   5. 글자가 대응될 경우 idx++을 해준다.
      1. 만약 pattern의 문자열 길이(n2)-1과 idx가 같아진다면 매칭이 성공되었으므로 카운트해준다.
2. 기존 룰렛의 크기(a)와 1번에서 구한 매칭되는 횟수(b)의 최소 공배수(lcd(a,b))를 구한 다음 각 값에 이를 나누어 출력한다.

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++) {
			sb.append(st.nextToken());
		}
		String pa = sb.toString();
		
		st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();
		for(int i=0; i<n; i++) {
			sb.append(st.nextToken());
		}
		String pattern = sb.toString();
		
		int a = pa.length();
		int b = kmp(pa+pa, pattern);
		int g = gcd(a,b);
		System.out.println((b/g) +"/" + (a/g));
		
	}
	
	static int gcd(int a, int b) {
		while(b>0) {
			int r = a%b; 
			a=b;
			b=r;
		}
		return a;
	}
	
	static int kmp(String parent, String pattern) {
		int n1 = parent.length();
		int n2 = pattern.length();
		int[] table = makeTable(pattern);
		int idx=0;
		int cnt =0;
		for(int i=0; i<n1-1; i++) {
			while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(parent.charAt(i) == pattern.charAt(idx)) {
				if(n2-1 == idx) {
					cnt++;
					idx = table[idx];
				}else {
					idx+=1;
				}
			}
		}
		return cnt;
	}
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		int idx=0;
		for(int i=1; i<n; i++) {
			while(idx>0 && pattern.charAt(i)!= pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}