[백준] #5525: IOIOI

1. Problem Link

• https://www.acmicpc.net/problem/5525

2. Notation

• s: input string that is only consisted of 'I' and 'O'
• n: number of 'O'
• m: length of s
• start: every index of 'I'
• cnt: number of 'OI' followed by start

3. Source Code

• find 'I' first.
• get number of 'OI' followd by 'I' index.
• jump as much as index used to get number of 'OI'

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val m = br.readLine().toInt()
    val s = br.readLine()

    var start = 0
    var answer = 0

    while (start < m) {
        if (s[start] == 'I') {
            val (cnt, newStart) = getNumberOfOI(s, m, start + 1)
            // ex. IOIOIOI
            // cnt = 3
            // n = 2
            // answer += (3 - 2 + 1)
            if (cnt >= n) answer += (cnt - n + 1)
            start = newStart
        } else start++
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

fun getNumberOfOI(s: String, m: Int, index: Int): Pair<Int, Int> {
    var _index = index
    var cnt = 0

    // find 'OI'
    while (_index < m - 1 && s[_index] == 'O' && s[_index + 1] == 'I') {
        cnt++
        _index += 2
    }

    return Pair(cnt, _index)
}

4. Complexity

• Time: O(m)
• Space: O(s.length)