[Kotlin] 백준 1874 : 스택 수열

문제 링크

1874번: 스택 수열

---

---

문제 해설

문제를 이해하기만 하면 스택을 이용하여 손쉽게 풀 수 있다. 예제 입출력의 경우를 예로 들어 보자.

4, 3, 6을 수열에 넣기 위한 동작을 그림으로 표현하면 다음과 같다.

그림에 대해 설명하자면 처음에 수열에 4를 추가해야 하는데 스택에 4가 없기 때문에 1, 2, 3, 4를 차례대로 삽입한다. 이후 스택의 맨 위에 있는 4를 제거하여 수열에 추가한다. 다음 수로 넘어가면 스택의 맨 위에 3이 있으므로 제거하여 수열에 추가한다. 다음 수로 넘어가면 스택의 맨 위에 6이 없기 때문에 마지막으로 추가한 4 이후의 수인 5, 6을 차례대로 삽입한다. 이후 스택의 맨 위에 있는 6을 제거하여 수열에 추가한다.

 

일련의 과정을 거치는 동안 수열에 추가해야하는 수가 스택에 삽입해야하는 다음 수보다 작을 경우엔 스택 수열을 만들 수 없으므로 "NO"를 출력한다.

---

Code

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val stack = Stack<Int>()
    val arr = IntArray(readLine().toInt()) { readLine().toInt() }
    var curr = 1
    for (num in arr) {
        // 추가해야 하는 수가 수열의 현재 수 이하면 스택에 계속 추가
        while (curr <= num) {
            stack.push(curr++)
            sb.append("+\n")
        }
        // 스택의 가장 위 값이 수열의 현재 수와 같으면 스택에서 제거
        if (stack.peek() == num) {
            stack.pop()
            sb.append("-\n")
        } 
        // 스택의 가장 위 값이 수열의 현재 수와 다르면(크면) 더 작은 수를 추가할 수 없으므로 프로그램 종료
        else {
            println("NO")
            return@with
        }
    }
    println(sb)
}