[백준] 1871번: 스택 수열 - Kotlin[코틀린]

문제

 

1874번: 스택 수열

 

---

풀이

 

 주여진 수열을 만들기 위해 스택의 push와 pop 과정을 통해 구현하는 문제이다. 먼저 예제 입력 1을 예시로 수열을 만드는 방법을 살펴보자. 4를 수열에 배치하기 위해서 스택에 1, 2, 3, 4를 넣어 {1, 2, 3, 4}인 상태를 만들고 4를 빼주면 된다. 수열은 [4]이 되고 스택은 {1, 2, 3}인 상태가 된다. 다음 3을 배치하기 위해 스택에서 3을 빼준다. 스택은 {1, 2}가 되고 수열은 [4 3]이된다. 모든 입력을 차례대로 표현하면 다음과 같다.

입력	스택	수열
4	1, 2, 3	4
3	1, 2	4 3
6	1, 2, 5	4 3 6
8	1, 2, 5, 7	4 3 6 8
7	1, 2, 5	4 3 6 8 7
5	1, 2	4 3 6 8 7 5
2	1	4 3 6 8 7 5 2
1		4 3 6 8 7 5 2 1

 

 현재 수열에 출력을 나타대는 변수 cur를 선언한다. 수열의 원소를 입력받은 후, 이 값이 cur보다 크다면 두 값의 차이만큼 스택에 push 연산을 해준다. push 연산이 끝난 후, 스택의 가장 상단에는 수열에 배치해야 할 수가 된다. 따라서 pop 연산을 수행하여 스택의 가장 위에 있는 수가 원래의 수열의 순서와 일치하는지 확인하고, 일치하지 않는 경우 불가능한 수열로 판단하여 'NO'를 출력한다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()

    val num = br.readLine().toInt()
    val stack = Stack<Int>()
    var cur = 0 // 수열에 출력한 수를 나타내는 변수
    var check = false

    repeat(num) {
        val tmp = br.readLine().toInt()
        if(!check) {
            if(cur<tmp) { // 스택에 출력할 수를 담을때 까지 push
                for(j in cur+1 .. tmp) {
                    stack.push(j)
                    sb.append("+\n")
                }
            }
            if(stack.pop()!=tmp) { // 수열이 불가능한 경우
                sb.clear()
                sb.append("NO")
                check = true
            } else {
            	sb.append("-\n")
            	cur = tmp
            }
        }
    }

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}