[Kotlin] 백준 4949 : 균형잡힌 세상

문제 링크

4949번: 균형잡힌 세상

---

---

문제 해설

스택을 이용하여 풀 수 있는 괄호 문제다. 문자열에서 괄호 외의 다른 문자는 모두 무시하고 괄호의 경우만 계산하면 되는데 모든 괄호가 짝을 이루되, 5번의 조건과 같이 괄호 내부에서도 괄호가 짝을 이뤄야 한다. 예를 들어 "[(])"의 경우는 대괄호 안에 소괄호는 왼쪽과 오른쪽이 모두 존재하지만 대괄호 사이에는 왼쪽 소괄호가, 소괄호 사이에는 오른쪽 대괄호가 있어서 짝을 이루지 못하므로 균형잡힌 문자열이 아니다.

 

스택을 이용하여 문제를 푸는 과정은 다음과 같다.

1. 문자열을 처음부터 끝까지 이동하면서 현재 문자가 왼쪽 괄호면 스택에 삽입한다.
2. 현재 문자가 오른쪽 괄호면 다음 경우로 나뉜다.
   • 현재 문자가 오른쪽 소괄호이고 스택의 맨 위 요소가 왼쪽 소괄호라면 소괄호가 짝을 이룬 경우이므로 스택에서 문자 하나를 제거한다.
   • 현재 문자가 오른쪽 대괄호이고 스택의 맨 위 요소가 왼쪽 대괄호라면 대괄호가 짝을 이룬 경우이므로 스택에서 문자 하나를 제거한다.
   • 두 경우 모두 스택이 비어있거나 다른 왼쪽 괄호가 나온다면 균형잡힌 문자열이 아니므로 버퍼에 "no"를 저장하고 다음 케이스로 넘어간다.
3. 문자열의 끝까지 검사를 마쳤다면 스택이 비어있는지 검사한다. 스택이 비어있다면 모든 괄호가 짝을 이룬 경우이므로 "yes"를, 스택이 비어있지 않다면 짝을 이루지 못한 괄호가 남아있는 경우이므로 "no"를 버퍼에 저장하고 다음 케이스로 넘어간다.

주의할 점은 스택이 비어있는데 스택의 맨 위 요소를 가져오려고 하면 EmptyStackException이 발생하기 때문에 스택의 맨 위 요소를 검사할 때 스택이 비어있는지도 같이 검사해야 한다.

---

Code

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    var str: String
    loop@ while (readLine().also { str = it } != ".") {
        val stack = Stack<Char>()
        for (c in str) {
            when (c) {
                '(', '[' -> stack.push(c)
                ')' -> {
                    if (stack.isNotEmpty() && stack.peek() == '(') stack.pop()
                    else {
                        bw.write("no\n")
                        continue@loop
                    }
                }

                ']' -> {
                    if (stack.isNotEmpty() && stack.peek() == '[') stack.pop()
                    else {
                        bw.write("no\n")
                        continue@loop
                    }
                }
            }
        }

        bw.write(if (stack.empty()) "yes\n" else "no\n")
    }
    bw.close()
}