1874번 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

스택을 통하여 해당 수열을 만들 수 있는지 묻는다. 

만들 수 있다면 해당 수열을 만들어가는 스택연산 과정을 출력하며

만들 수 없다면 No를 출력한다. 

 

접근 1  

 

1. 기준이 되는 숫자는 1부터 차례대로 증가한다. 

2. 스택 연산의 과정을 출력해야 하기에 해당 연산을 실제로 따라갈 필요가 있다. 

 

접근 2

 

1. 스택 연산의 과정을 따라가야 한다.

2.기준 수열는 증가하기만 한다. f(x) = n 

 

해결 과정

 

1. 만들어야 하는 수의 배열을 입력 받는다,(inputList)

2. 기준 수(head)와 스택을 이용하여  해당 수열을 만들 수 있어야 한다. 

3. 만들어야 하는 수열을 처음부터 끝까지 순회한다. 

4. 연산에 사용할 stack또한 하나 필요하다. 

5. 초기에 1은 무조건 stack에 들어있는 상태로 가정한다. 

 

 

 

스택 수열 연산 과정

* stack은 가장 위의 값만을 열람할 수 있기에  inputList[i]의 값은 스택의 가장 위 혹은 기준 수와 같아야 한다.  

 

1.  inputList[i]값과 head의 값을 비교하여, pop한다

2. inputList[i]값이 더 작다면 stack에 push를 하고 head값을 증가시킨다 

3. inputList[i]값이 더 큰 경우 stack의 가장 위 값(peek)을 검사하고 같다면 스택에서 pop을 한다,  스택이 비어있거나 peek값이 inputList[i] 와 다르다면 해당 수열은 만들 수 없는 수열이다. 

4. 1-3의 과정을 i를 하나씩 증가시켜가며 수열의 끝까지 진행한다.

 

전체 코드 

 

class StackNumArrays{

    val inputList = mutableListOf<Int>()

    val resultList = mutableListOf<Char>()

    fun inputStack(num: Int){
        inputList.add(num)
    }

    fun getResult(){
        val stack = Stack<Int>()
        var head = 1
        stack.add(1)
        resultList.add('+')
        inputList.forEach {


            while (true){
                if( it == head){
                    resultList.add('-')
                    if(stack.peek() == head){
                        stack.pop()
                    }
                    break
                } else if( it > head ){
                    resultList.add('+')
                    stack.push(++head)
                } else {
                    if(stack.empty()){
                        println("NO")
                        println(stack)
                        return
                    }

                    if(stack.peek() != it){
                        println("NO")
                        stack.pop()
                        return
                    }
                    stack.pop()
                    resultList.add('-')
                    break
                }
            }

        }

        resultList.forEach {
            println(it)
        }
    }


}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val input = readLine().toInt()

    val solution = StackNumArrays()

    for(i in 0 until input) {
        solution.inputStack(readLine().toInt())
    }

    solution.getResult()

    return@with

}