백준 4949 균형잡힌 세상 - [알고리즘] [kotlin] [stack]

문제 내용

문제 분석

1. 소괄호 대괄호가 적절히 열리고 닫히는지 검사해야 한다.

2. 괄호 안의 문자열 안의 문자열도 검사를 해야한다.

3. 마지막은 온점으로 끝난다.

4. 문자열이 없거나 소괄호 대괄호가 없는 경우도 균형잡힌 문자열이다.

5. 마지막으로 들어오는 "."은 종료조건이므로 "yes"를 출력하면 안된다.

 

아이디어

1. 열리는 괄호와 닫히는 괄호가 매칭되는지 검사한다.

2. 올바른 형태라면, 닫히는 괄호가 들어왔을 때 가장 최근에 들어온 괄호와 짝이 맞아야 한다.

// 만약 짝이 없다면 올바른 형태가 아니다 ex) "abcd)abc", "abc)abc(abc"

// 만약 짝이 다르다면 올바른 형태가 아니다 ex) "abc[abc)"

3. 가장 최근의 괄호와 비교하기 위해 stack 자료구조를 사용한다.

4. 문자열을 비교할 필요가 없으므로 stack에 넣지 않는다.

5. 온점이 나오면 작업을 중지하고 이때, stack에 남은 괄호가 0개라면 균형잡힌 문자열로 판단한다.

 

풀이

import java.util.*

fun main () {
    System.`in`.bufferedReader().use { br ->
        val sb = StringBuilder()

        for(str in br.readLines()) {
            if(str == ".") break
            val stack = LinkedList<Char>()
            for(c in str) {
                // 열리는 괄호는 stack에 넣는다.
                if(c == '(' || c == '[') stack.addLast(c)
                // 닫히는 괄호들은 종류에 따라 올바른 문자열인지 판단한 후,
                // 올바르지 않다면 stack에 'x'를 넣어 표시하고 반복문을 탈출한다.
                else if (c == ')' || c == ']') {
                    // 와야 할 열리는 괄호를 의미
                    val targetOpen = if(c == ')') '(' else '['
                    if(stack.isEmpty() || stack.last != targetOpen) {
                        // 이전 열린 괄호가 없는 경우 || 올바르지 않은 열린 괄호가 온 경우
                        stack.addLast('x')
                        break
                    }
                    // 올바른 경우라면 열리는 괄호를 stack에서 제거
                    stack.removeLast()
                    // 상단 if문에서 검사할 때 last 대신 removeLast를 사용하면 이 부분을 생략할 수 있지만
                    // 가독성을 위해 그러지 않겠다.
                }
            }

            sb.append(if(stack.isEmpty()) "yes\n" else "no\n")
        }

        print(sb.toString())
    }
}