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

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

11585번: 속타는 저녁 메뉴

문제

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

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

입력

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

출력

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

알고리즘 분류

• 문자열
• kmp

풀이

오랜만에 kmp 문제

하.. 최근 면접에서 kmp 얘길 했는데.. 복습좀 해둘걸...

우선 Parent 문자열은 원형이기 때문에 그냥 오른쪽에 이어 붙인다.

IWANTMEAT + IWANTMEAT 문자열에 KMP를 돌려 pattern이 몇 번 나오는지 세면 된다.

여기서 주의할 점은 parent 문자열 두 개를 그냥 이어 붙이면 IWANTMEAT를 두 번 확인할 수 있기 때문에 마지막 문자를 빼준다.

그럼 최종적으로 Parent는 IWANTMEAT + IWANTMEA이 된다.

cnt = kmp 알고리즘으로 parent에 pattern이 나오는 횟수

n = 기존 parent의 길이

이 두 값을 기약분수로 나타내야 하는데, 기약 분수랑 더 이상 약분이 안 되는 형태의 분수다.

이는 곧 분자와 분모의 최대공약수로 분자, 분모를 나눈 값을 출력하라는 의미로,

최대 공약수를 구하는 유클리드 호제 알고리즘을 이용할 수 있다.

 

kmp 알고리즘을 모른다면 풀기 어렵겠지만, 이대로 마치긴 아쉬우니 kmp 알고리즘에 대한 설명을 간략히 해본다.

 

kmp?

접두사와 접미사의 개념을 활용하여 반복되는 연산을 줄일 수 있는 문자열 매칭 알고리즘이다.

1. 실패 함수를 만든다.

실패 함수란 parent와 pattern의 매칭에 실패했을 때 처리를 도울 배열을 만든다.

이때 접두사와 접미사를 이용하여 매칭에 실패했을 때 특정 길이만큼 건너뛰고 탐색을 이어나갈 수 있다.

이를 통해 만들어지는 배열을 pi 배열이라 하는데, 왜 pi인지는 못찾았다.

무튼 pi배열의 크기는 pattern의 길이와 같으며, 해당 인덱스까지 pattern의 접두사와 접미사가 같은 길이를 저장한다.

 

2. parent 문자열과 pattern 문자열을 매칭한다.

기존 완전 탐색을 생각하면 Parent의 i번 째 인덱스와 Pattern의 j번 째 인덱스를 비교했을 때

parent[i] != pattern[j]라면 i는 i+1로 넘어가고, j는 다시 0부터 시작한다.

즉, parent의 모든 i에 대해 pattern의 크기만큼 다 비교를 해야 하기 때문에 나이브하게 짠다면 O(N*M)의 시간 복잡도가 되는 것이다.

N = parent 길이

M = pattern 길이

kmp는??

위에서 만들어놓은 pi배열을 이용한다.

parent[i] != pattern[j] 라면 i는 완탐과 동일하게 i+1, j는 pi[j-1]로 이동한다.

pi[j-1]이란 j이전 인덱스까지 접두사와 접미사가 같은 길이를 의미하고, 이 길이만큼 스킵하고 탐색할 수 있다는 의미이다.

zzababzzzz : parent

ababbb : pattern

001200 : pi

라고 하면 parent의 3번째 z (6번째 인덱스)를 만났을 때 pattern은 3번째 b (4번째 인덱스)를 비교할 차례이고

두 값이 같지 않다.

여기서 완탐과 kmp의 차이는 완탐이라면 pattern은 다시 0번 인덱스부터 탐색할텐데 kmp는 두 번째 a (2번째 인덱스)부터 탐색하게 되는 것이다.

왜냐면 parent 에서 abab의 빨간 부분은 이미 pattern의 abab의 빨간 부분과 같기 때문이다.

이 부분은 kmp 알고리즘을 모른다면 이해하기 어려우니 kmp 먼저 공부하도록 하자

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun makeTable(pattern: String): IntArray{
    val pi = IntArray(pattern.length)
    var j = 0
    for(i in 1 until pi.size){
        while(j > 0 && pattern[i] != pattern[j]){
            j = pi[j-1]
        }
        if(pattern[i] == pattern[j]){
            pi[i] = ++j
        }
    }
    return pi
}

fun kmp(parent: String, pattern: String, pi: IntArray): Int{
    var i = 0
    var j = 0
    var cnt = 0
    while(i < parent.length){
        if(parent[i] == pattern[j]){
            if(++j == pattern.length){
                cnt++
                j = pi[j-1]
            }
        }else{
            if(j > 0) j = pi[j-1]
        }
        i++
    }
    return cnt
}

fun getGcd(low: Int, high: Int): Int{
    return if(high%low == 0) low
    else getGcd(high%low, low)
}

fun main() = with(System.out.bufferedWriter()){

    val n = getInt()
    val input = br.readLine().replace(" ","")
    val parent = "$input${input.substring(0,input.lastIndex)}"
    val pattern = br.readLine().replace(" ","")
    val pi = makeTable(pattern)
    val cnt = kmp(parent,pattern,pi)
    val gcd = getGcd(cnt,n)
    write("${cnt/gcd}/${n/gcd}")
    close()
}