[백준] 스택 수열 (1874)(kotlin)

문제 설명

백준 1874번 문제 링크

입력 및 출력

» 입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

» 출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입출력(테스트케이스)

입력	출력
8 4 3 6 8 7 5 2 1	+ + + + - - + + - + + - - - - -
5 1 2 5 3 4	NO

문제 힌트

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

문제 풀이1

import java.util.Stack

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val stack = Stack<Int>()
    val n = readLine().toInt()
    val charArr = mutableListOf<Char>() // '+'와 '-'를 차례대로 저장할 리스

    var next = readLine().toInt()
    var count = 1   // 2 ~ n + 1까지의 입력만 받기 위한 플래그

    for (i in 1..n) {   // 1부터 n까지 탐색
        stack.push(i)   // i를 stack에 push
        charArr.add('+')    // push가 일어났으므로 '+' 추가

        // 입력 받은 수열의 숫자가 stack의 마지막에 저장된 것과 동일하면 반복문 실행
        while (next == stack.peek()) {
            stack.pop() // stack을 pop
            charArr.add('-')    // pop동작이 일어났으므로 '-'

            // 수열의 갯수를 초과해서 입력받지 않도록 입력 카운트가 n개를 넘지 않도록 확인
            if (count < n) {
                next = readLine().toInt()   // 새로운 수열의 수를 입력 받음
                count++ // 입력 받은 수열의 갯수 1증가
            }

            // stack이 비어있으면 비교할 수가 없으므로 반복문 break
            if (stack.isEmpty()) break
        }
    }

    // 작업이 모두 끝나고 stack이 비어있지 않으면 수열이 아니므로 "NO"
    if (stack.isNotEmpty()) println("NO")
    else println(charArr.joinToString("\n"))
}