11585번: 속타는 저녁 메뉴

문제 출처 : https://www.acmicpc.net/problem/11585

11585번: 속타는 저녁 메뉴

언어 : Kotlin

 

문제 설명 :

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

 

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

 

입력 :

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

 

출력 :

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

 

제한 사항 :

• 시간 제한 : 5초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
9 I W A N T M E A T E A T I W A N T M	1/9
6 A A B A A B B A A B A A	1/3

 

풀이 : 

"BCA"일때 고기를 먹을 수 있고, 주어진 룰렛은 "ABC"일때 이를 표로 만들어내어 확인해보면 다음과 같다.

 

A	B	C	cnt
	B	C	0

 

단순히 룰렛 하나로 따지면 BCA가 완성될 수 없으므로 고기를 먹을 수 있는 경우의 수는 존재하지 않는다.

그렇기 때문에 문제에선 고기를 먹을 수 있는 경우의 수는 적어도 한 가지 이상 있기에 분자가 0이 되는 경우는 없다고 했다.  이를 토대로 한번이라도 먹을 수 있게 바꾸면 다음과 같아진다.

 

A	B	C	A	B	C	cnt
	B	C	A			1
				B	C	0

 

룰렛의 크기를 2배로 만들어주면 주어진 룰렛과 먹을 수 있는 경우에 따라 다르겠지만 최소 1번 이상은 먹을 수 있게 만들어진다는 것.

 

문제에서 룰렛의 칸 수의 범위는 1 ~ 1,000,000이다.

무작정 비교를 시작하면 시간제한에 걸릴 것이므로 KMP 문자열 매칭 알고리즘을 사용해야한다.

문자열 알고리즘은 여러 종류가 존재하는데 KMP를 사용하는 이유는 간단하다.

단순히 문자열 매칭을 돌리는 것은 위에서 말했듯 시간제한에 걸리며, 오토마타라는 알고리즘은 KMP 알고리즘보다 설계하기에 앞서 고려해야할 것이 많고 어렵다. 라빈-카프 알고리즘은 해시값을 비교하는 것으로 문자열이 커질 경우 충돌현상이 일어날 수 있어 불안정하고 비효율적이다.

 

따로 최장 공통 부분 문자열 관련 알고리즘도 존재하나 이는 문제와 맞지 않다. 그렇기에 KMP다.

라이브러리 내장 함수를 사용해도 좋으나 KMP보단 느리다고한다.

 

KMP 알고리즘을 사용할 때, pattern의 매칭 대상이 되는 str(룰렛)은 2배 늘려준다고 했는데 중복을 제거하기 위해 마지막 문자는 제거한다. 이후 구해진 카운트 숫자를 기약분수를 통해 나타내라 했으므로 최대공약수 GCD를 사용한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val input = readLine().replace(" ", "").repeat(2).dropLast(1)
    val pattern = readLine().replace(" ", "")
    val cnt = kmp(input, pattern)
    val gcd = gcd(cnt, n)

    bw.write("${cnt / gcd}/${n / gcd}")
    bw.flush()
    bw.close()
}

fun gcd(a: Int, b: Int): Int = if (b != 0) gcd(b, a % b) else a

fun kmp(str: String, pattern: String): Int {
    val idxArr = IntArray(2)
    val arr = makeTable(pattern)
    var cnt = 0

    for (i in idxArr[0] until str.length) {
        if (str[i] == pattern[idxArr[1]]) {
            if (++idxArr[1] == pattern.length) {
                idxArr[1] = arr[idxArr[1] - 1]
                cnt++
            }
        } else {
            if (idxArr[1] > 0) idxArr[1] = arr[idxArr[1] - 1]
        }

        idxArr[0]++
    }

    return cnt
}

fun makeTable(pattern: String): IntArray {
    val arr = IntArray(pattern.length)
    var idx = 0

    for (i in 1 until arr.size) {
        while (idx > 0 && pattern[i] != pattern[idx]) {
            idx = arr[idx - 1]
        }

        if (pattern[i] == pattern[idx]) arr[i] = ++idx
    }

    return arr
}