[백준] 4949번 균형잡힌 세상(Stack - 스택)[Kotlin - 코틀린]

백준 4949번 문제입니다. (solved.ac) 기준 실버 4 문제입니다.

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

문제

문제 접근

알파벳, 공백, 소괄호( '(', ')' ), 대괄호( '[', ']' )로 이루어진 문자열을 입력받고, 해당 문자열에서 괄호들의 균형이 잘 맞춰져 있는지 확인하여 균형이 맞다면 yes를 그렇지 않다면 no를 출력하는 문제입니다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

이 다섯가지 설명을 기반으로 문제 해결을 위하여 간단하게 접근할 수 있습니다.

 

우선 괄호들이 들어갈 Stack<Char>의 stack을 만들어줍니다.

문자열을 입력받으면 forEach를 사용하여 문자열을 하나하나 탐색하는데, 오직 괄호만의 균형을 판단하면 되기 때문에 나머지 문자는 고려하지 않도록 코드를 구성하였습니다. 

일반적으로 괄호는 stack에 담기게 됩니다.

단, stack에 담겨있는 마지막 괄호가 여는 괄호( '(', '[' )일 때 현재 괄호가 해당괄호와 짝이 맞는 괄호라면 괄호를 stack에 넣지 않고 마지막 괄호를 stack에서 pop시켜줍니다.(괄호가 짝이 맞았으므로 계산에서 제외한다는 뜻) 

ex) stack 에 [ '(', '(' ] 와 같은 형태로 담겨있을 때 현재의 괄호가 ')'라면 stack은 [ '(' ]로 되게 됩니다.

문자열의 끝까지 위의 과정을 거친 후 stack에 값이 담겨있다면 균형이 맞지 않는 것, stack이 비어있다면 균형이 맞다는 소리입니다.!

정답 코드

import java.util.Stack

fun main() {

    // 괄호가 담길 stack
    val stack = Stack<Char>()

    while (true) {

        // 입력 받은 문자열
        val string = readln()

        // "."가 입력되면 실행 종료
        if (string == ".") return

        // 문자열을 순회하기
        string.forEach { curChar ->

            // 스택에 있는 마지막 괄호
            val lastStackElement = if (stack.isNotEmpty()) stack.peek() else null

            // 괄호일 경우만 고려
            if (curChar == '[' || curChar == ']' || curChar == '(' || curChar == ')') {

                // 스택에 담긴 마지막 괄호가 ( 일 때
                if (lastStackElement == '(') {

                    // 현재 문자가 )라면 짝을 이룬다는 뜻이므로 괄호 제거 판정
                    if (curChar == ')') stack.pop()
                    // 짝을 이루지 않는다면 스택에 괄호 삽입
                    else stack.add(curChar)

                    // 스택에 담긴 마지막 괄호가 [ 일 때
                } else if (lastStackElement == '[') {

                    // 현재 문자가 ] 라면 짝을 이룬다는 뜻이므로 괄호 제거 판정
                    if (curChar == ']') stack.pop()
                    // 짝을 이루지 않는다면 스택에 괄호 삽입
                    else stack.add(curChar)

                    // 스택에 담긴 마지막 괄호가 ], )라면 균형이 지어질 수 없으므로 스택에 괄호 삽입
                } else stack.add(curChar)

            }
        }

        // 균형이 잡혀있다면 yes 아니라면 no 출력
        if (stack.isEmpty()) println("yes") else println("no")
        // 스택 비우기
        stack.clear()

    }

}