[백준] 5525번 IOIOI in Kotlin

📜 문제

문제 링크

💡 틀린 풀이

문자열 S에 있는 모든 문자들을 순회하면서 (i-1)번째 문자가 'I'인 경우에만 index(i ~ i+2n)의 substring이 Pn을 만족하는지 확인했다.

여기서 나의 실수는 substring과 Pn을 비교하는 과정에서, Pn의 문자열의 길이가 M이라는 가정 하에 O(N)의 시간이 걸린다는 걸 간과했기 때문이었다. 입력받은 전체 문자열의 길이 M만큼만 순회하기 때문에 O(M)의 시간이 걸린다고 착각했던 것이다!😅

⌨️ 틀린 코드

fun main() = with (System.`in`.bufferedReader()) {
        val n = readLine()!!.toInt()
        val m = readLine()!!.toInt()
        val inputString = readLine()!!

        var result = 0
        var pn = "I"

        repeat(n) {
            pn += "OI"
        }

        for (i in 0 until m - 2 * n) { // O(NM)
            if (inputString[i] == 'I') {
                val tmpString = inputString.substring(i, i + 2 * n + 1)
                if (tmpString == pn) result++
            }
        }

        println(result)
}

💡 정답 풀이

문자열 S에 있는 모든 문자들을 순회하면서 i번째 문자가 "I"일 때, S의 부분 문자열 S[i~i+2]과 "IOI"와 비교하면서 "IOI"가 연속으로 몇번 나왔는지 담는 변수로 continuousIOICount를 두었다. 예시로, "IOIOIOI"의 경우 continousIOICount가 3이 된다.
문자열 S를 순회하면서 새로운 "IOI"를 발견했을 때 continuousIOICount보다 n이 작으면 새로운 Pn이라고 판단하는 방식으로 문제를 풀었다.

문자열 S에 있는 모든 문자들을 순회하는 건 앞의 틀린 풀이와 동일하지만, 문자열 비교를 "IOI"로, 3개의 문자로만 이루어진 문자열을 비교하는 방식으로 바꾸었다. 따라서 O(NM)을 O(3M)으로 시간복잡도를 줄일 수 있었다.

⌨️ 정답 코드

fun main() = with (System.`in`.bufferedReader()) {
        val n = readLine()!!.toInt()
        val m = readLine()!!.toInt()
        val inputString = readLine()!!

        var result = 0
        var continuousIOICount = 0

        for (i in 0..(m - 3)) { // O(3N)
            if (inputString[i] == 'I') {
                if (inputString[i + 1] == 'O' && inputString[i + 2] == 'I') {
                    continuousIOICount++
                    if (n <= continuousIOICount) result++
                }
                else {
                    continuousIOICount = 0
                }
            }
        }

        println(result)
}