[ 백준 4354 ] - 문자열 제곱 (Kotlin)

 

4354번: 문자열 제곱

 

 

문제 이해 & 기본 개념

s = a ^ n을 만족하는 최대의 n을 구해야하는 문제이므로,

a의 길이가 가장 작은 경우를 찾아야하는 문제이다.

 

해당 문제는 kmp 알고리즘 중에서 최대 접두부 테이블을 이용하여 풀 수 있는데,

 

 

예시로 "ababab" 에 대한 최대 접두부 테이블은 아래와 같다.

a	b	a	b	a	b
0	0	1	2	3	4

테이블을 잘 보면 처음 ab에선 0 0이고 그 이후부턴 1 2 3 4로 계속 이어지는 것을 볼 수 있다.

 

즉, 테이블의 값이 증가하기 전 부분 (ab)가 계속 반복되고 있다는 것을 캐치하는 것이 가장 중요하다.

 

이 문제의 중요 포인트를 정리해보면 아래와 같다.

---

중요 포인트

1. 테이블의 값이 1이 된 순간이 문자열의 접두사와 일치가 시작된 순간이라는 것
2. 값이 계속 이어지면 그 앞 부분의 문자열이 계속 반복되고 있다는 뜻이라는 것

 

이 두 가지 포인트가 해당 문제의 핵심이라고 할 수 있다.

 

테스트 케이스 몇 가지를 살펴 보면,

테스트 케이스

첫 번째 테스트 케이스에서 "abcabcabc"의 경우 "abc"가 계속 반복 되어서  0 0 0 이후에 1 2 3 4 5 6으로 이어지는 것을 볼 수 있다.

 

두 번째 테스트 케이스는 "aabbccdd"인데, 끝까지 반복 되는 경우가 없어서 테이블의 값이 이어지지 않는 것을 볼 수 있다.

---

최종 풀이

최대 접두부 테이블을 통해서 반복되는 문자열이 어느 부분인지 알 수 있었고, 해당 문자열을 찾기 위해서는 테이블의 마지막 값을 이용하면 된다.

 

(원본 문자열 길이 - 테이블의 마지막 값) = 반복되는 문자열의 길이

위처럼 반복되는 문자열의 길이를 구했으면 s = a^n 에서 s와 a를 알고 있는 것이다.

 

n을 구하기 위해선 s / a를 해주면 되므로 최종 식은 아래와 같다.

 

원본 문자열 길이 / (원본 문자열 길이 - 테이블의 마지막 값)

fun solve(str:String):Int{
    val last = makeTable(str)
    val remain = str.length % (str.length - last)
    val div = str.length / (str.length - last)

    return if(remain == 0) div else 1
}

 

 

주의할 점

s = a ^ n을 만족하려면 반복되는 문자열이 마지막까지 이어져야한다는 뜻이다. (단순히 문자열 안에서 반복만 되면 안된다.)

 

"abababc" 처럼 ab가 여러번 반복 되더라도 마지막에 "c"가 있어서 s = a ^ n을 만족할 수 없다.

 

원본 문자열 길이에서 반복되는 문자열의 길이를 나누었을 때, 딱 떨어지는지 확인해야한다.

    val remain = str.length % (str.length - last) // 원본 문자열을 반복 문자열로 나눴을때 나머지
    val div = str.length / (str.length - last)

    return if(remain == 0) div else 1 // 딱 나누어 떨어지면 n을 리턴, 그렇지 않으면 1 리턴

 

소스 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun makeTable(p:String): Int{
    val table = Array(p.length){0}
    var j = 0

    for (i in 1 until p.length){
        while(j > 0 && p[i] != p[j]) j = table[j-1]

        if(p[i] == p[j]) table[i] = ++j
    }

    return table.last()
}

fun solve(str:String):Int{
    val last = makeTable(str)
    val remain = str.length % (str.length - last)
    val div = str.length / (str.length - last)

    return if(remain == 0) div else 1
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var str:String
    val sb = StringBuilder()

    while(true){
        str = readLine()
        if(str == ".") break

        sb.append(solve(str)).append("\n")
    }
    print(sb.toString())
}