[백준] #4889: 안정적인 문자열

1. Problem Link

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

2. Source Code

• If the parenthsis is eqaul to '{', just add to stack.
• If the parenthisis is equal to '}', check weather stack is empty or not.
• If the stack is empty, count up the change count. It means change '}' to '{' to make stable string.
• If the stack is not empty, just pop the stack.
• Finally, count up the stack size divided by two.
• I think the finally step is quite hard to understand directly. So, let's assume that two '{' remain in stack which is '{{'.
• To make string stable, one of '{' must change to '}'. So, 1 will be counted up.

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

    var cnt = 1
    while (true) {
        val parentheses = br.readLine()
        if (parentheses[0] == '-') break

        var changeCnt = 0
        val stack = mutableListOf<Char>()
        for (parenthesis in parentheses) {
            if (parenthesis == '{') stack.add(parenthesis)
            if (parenthesis == '}') {
                if (stack.isEmpty()) {
                    stack.add('{')
                    changeCnt++
                } else {
                    stack.removeLast()
                }
            }
        }
        changeCnt += stack.size / 2

        bw.write("$cnt. $changeCnt\n")
        cnt++
    }

    br.close()
    bw.close()
}

3. Complexity

• Time: O(N), N is length of string
• Space: O(N)