[백준 알고리즘/Kotlin] 1847번 스택 수열 (feat. Stack, 스택 관련 메서드)

 

저는 처음에 이 문제를 접했을 때에는 풀이 방법을 생각하지 못했습니다.

그러나 아래와 같이 로직을 정리하고, 코드를 작성해보도록 하겠습니다.

 

1. 만들어야 하는 수열을 순서대로 읽으면서 해당 숫자가 스택의 top에 있지 않다면,
   그 숫자가 나올 때까지 스택에 숫자를 push합니다.
   이 때, push하는 숫자는 1부터 n까지 순서대로 push하고, 각 push 연산마다 + 를 출력합니다.

2. 만약 스택의 top에 있는 숫자가 현재 수열에서 읽은 숫자와 같다면,
   스택에서 그 숫자를 pop하고 - 를 출력합니다.

3. 만약 스택의 top에 있는 숫자가 현재 수열에서 읽은 숫자보다 크다면,
   주어진 수열을 만들 수 없는 경우이므로 NO를 출력하고 프로그램을 종료합니다.

 

스택의 top에 있는 수가 현재 수열에서 읽은 수보다 클 경우 NO를 출력하는 이유에 대해

아래의 예시를 보며 자세히 살펴보죠. (예제 입력 2를 예시로 들어보도록 하겠습니다.)

5
1
2
5
3
4

n = 5
1일 경우 stack = [1] → 스택의 top이 1이므로 pop() → stack = []
2일 경우 stack = [2] → 스택의 top이 2이므로 pop() → stack = []
5일 경우 stack = [3, 4, 5] → 스택의 top이 5이므로 pop() → stack = [3, 4]
3일 경우 stack = [3, 4] → 스택의 top이 4이므로 3 != 4 → 주어진 수열을 만들 수 없다.

∴ NO 출력

 

이를 코드로 풀어보도록 하겠습니다.

 

최종 코드

import java.lang.StringBuilder
import java.util.Stack

fun main() = System.`in`.bufferedReader().use { br ->
    val n = br.readLine().toInt()
    val stack = Stack<Int>()
    val result = StringBuilder()
    var current = 1 // 스택에 push 할 숫자

    repeat(n) {
        val input = br.readLine().toInt()

        while (current <= input) {
            stack.push(current++)
            result.append("+\n")
        }

        if (stack.isNotEmpty() && stack.peek() == input) {
            stack.pop()
            result.append("-\n")
        } else {
            println("NO")
            return
        }
    }

    println(result)
}

 

Stack의 메서드

순번	메서드	설명
1	push(e)	스택의 맨 위에 요소 추가 (스택의 새로운 top)
2	pop()	스택의 맨 위에 요소 제거 및 반환 (없을 시 EmptyStackException)
3	peek()	스택의 맨 위에 요소 반환 (제거X, 없을 시 EmptyStackException)
4	empty()	비었는지 확인 (비어있으면 true, 아니면 false)
5	search(o)	스택의 top부터 아래로 찾아가며, top으로 부터 거리 반환 (없을 시 -1)
6	size()	스택의 요소 수 반환
7	capacity()	스택의 현재 용량 반환
8	contains(o)	포함 여부 확인 (포함 시 true, 아니면 false)
9	elementAt(i)	특정 위치에 있는 요소 반환
10	clear()	모든 요소 제거