스택 수열(백준)

package com.example.algorithm

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import java.util.Collections.max
import java.util.Collections.min


fun main(){

    val br = BufferedReader(InputStreamReader(System.`in`))
    //val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    val count = br.readLine().toInt()

    val stack = Stack<Int>()
    var max = 0
    var pop = 0
    var noCheck = false
    val result = mutableListOf<Char>()
    for(_i in 1..count){
        val input = br.readLine().toInt()


        if(pop == 0 || pop<=input){
            for(i in max+1..input){
                stack.push(i)
                result.add('+')
            }
        }
        while(input != pop){
            if(stack.empty()){
                noCheck = true
                break
            }
            pop = stack.pop()
            result.add('-')

        }
        if(noCheck)
            break


        if(max < pop){
            max = pop
        }
    }
    if(noCheck){
        println("NO")
    }
    else{
        for(ch in result){
            println(ch)
        }
    }
    br.close()

}

문제가 이해 안되서 유튜브에 있는 스택 수열을 알려주는 영상을 보며 이해를 한다음 풀었다.

알고리즘 원리는

1부터 스택을 쌓아가면서 push(+) 입력한수를 만나면 pop(-)하고 다음 수로 넘어간다.

그다음 부터가 중요하다. pop해왔던 수들의 max를 기억하고

max보다 작으면 계속 pop(-) 해서 찾고

max보다 크면 max 다음 수부터 push(+) 해서 찾는다.

이 때 pop(-)해서 못찾으면 스택 수열이 아닌 것이다.

 

백준 사이트에서 설명이 부족한 문제의 경우는 코딩 구현이 어렵지 않은 문제도 어려워 지는 경향이 있어서

설명을 이해하기 쉽고 상세하게 적어줬으면 좋을 것 같긴하다.