[BOJ:1701] Cubeditor

[코딩 스터디] Cubeditor

⬇️ 나의 코드 ⬇️(Kotlin)

fun main() {
    var input = readLine()!!

    var answer = 0

    for (i in 0 until input.length) {
        var pi = getPi(input.substring(i, input.length))
        if(pi > answer) answer = pi
        if(answer > input.length - 0) break
    }

    println(answer)
    return
}

fun getPi(sub: String): Int {
    var j = 0
    var pi = IntArray(sub.length) { 0 }

    for( i in 1 until sub.length) {
        while(j > 0 && sub[j] != sub[i]) j = pi[j-1].toInt()
        if(sub[i] == sub[j]) pi[i] = ++j
    }

    return pi.max()
}

🤧 풀이 방법

1. KMP알고리즘에서 PI값을 구하는 방식을 이용하여 문제를 풀었다. -> getPi사용
2. PI값을 이용하여 그 문자열에서 나올 수 있는 최대 PI값을 구한다. -> return max Pi
3. 이때 PI를 구하는 방식에서 중복되는 문자열의 시작 위치가 고정되어있기 때문에 모든 위치에서 시작하는 문자열에 대해 체크해야한다. -> for i in 0 until input.length

📚 풀면서 알게된 것

KMP 알고리즘은 문자열 검색 알고리즘으로 O(N+M)의 복잡도를 가집니다.

KMP알고리즘은 prefix == surfix인 길이를 이용하는 방식이다.
이때 PI라는 값을 이용하는데 PI는 부분 문자열에서 prefix == surfix 가 되는 부분 문자열 중에 가장 긴 것의 길이이다. 이를 이용해서 문제를 푸는데,

이와 관련된것은 따로 포스팅을 준비할 예정이다.

until은 endIndex 포함 X
..는 포함 O

부끄럽지만 헷갈렸던것,,, 어쩐지 마지막 숫자가 안뜨더라..

var pi = Array(sub.length) { 0 } 보다
var pi = IntArray(sub.length) { 0 }가 메모리 적으로 효율적이다.

그리고 1 ~ n 까지 증가하는 방식보다 n ~ 1로 감소하는 반복문을 쓰고 싶을때는
i in n downTo 1이런식으로 작성해

👀 다른 사람의 코드를 보고 알게된 것

📚 참고 자료

https://chanhuiseok.github.io/posts/algo-14/