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

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

4949번: 균형잡힌 세상

 

난이도 : 실버 4
태그 : 자료구조, 문자열, 스택

 

 

설명

모든 왼쪽 괄호는 오른쪽 괄호와 맞아야 합니다.

[](), [()] 등은 맞지만,

([], ([)] 등은 맞지 않습니다.

 

스택을 활용하기 좋은 문제일 것 같네요.

[()]을 예로 들겠습니다.

첫 번째 글자 : [

stack에 문자를 넣습니다.

현재 스택 : [

 

두 번째 글자 : (

stack이 비어있지 않으나, 가장 위 문자인 [는 (와 맞지 않습니다.

현재 스택 : [(

 

세 번째 글자 : )

stack의 가장 윗 문자는 '('입니다.

'('는 ')'와 짝을 이루는 문자열로,

스택에서 하나를 뺍니다.

현재 스택 : [

 

네 번째 글자 : ]

stack의 가장 문자는 '['으로 ']'와 짝을 이루는 문자열입니다.

스택에서 하나를 뺍니다.

현재 스택 : x

 

모든 문자열을 처리했으나 스택이 비어있습니다.

모든 괄호들이 짝이 맞은 것이지요.

 

 

반면, [(])는 어떨까요?

1 : '[' - stack - [

2 : '(' - stack - [(

3 : ']' - stack - [(]

4 : ')' - stack - [(])

스택이 비어있지 않으면 모든 괄호가 짝을 이룰 수는 없었다는 의미이기도 합니다.

[(])는 짝을 이룰 수 없는 형태입니다.

 

 

 

소스코드

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    while (true) {
        var line = readLine()
        if (line == ".") break
        // 괄호만 남기기
        line = line.filter { it in "([)]" }

        val stack = Stack<Char>()

        for (i in line) {
            when (i) {
                '(', '[' -> stack.add(i)
                ')' -> if (stack.isNotEmpty() && stack.peek() == '(') stack.pop() else stack.add(i)
                ']' -> if (stack.isNotEmpty() && stack.peek() == '[') stack.pop() else stack.add(i)
            }
        }

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

    print(sb)
}

 

 

 

후기

괄호 짝 맞추기 문제는 스택의 활용으로 자주 나오는 문제 중 하나입니다.

스택의 활용법을 연습하기 좋은 문제 중 하나죠.