[백준] 1874번 스택 수열: Python

1874번: 스택 수열

 

문제 해결 포인트

문제를 풀기 위해 스택 자료구조를 사용하지만 생각해볼 점이 많습니다.

 

• Pop이 발생한 뒤의 스택 상태는?
• Pop 이후 Push를 할 때 어떤 수가 입력되어야 할까?
• 어떤 경우에 수열 생성이 불가능할까?

  스택은 Last-in, First out(LIFO) 자료구조입니다. 가장 최근에 입력된 값이 제일 먼저 출력되며 가장 먼저 입력된 값은 가장 나중에 출력됩니다. 예제 입력 1을 고민해봅시다. 4까지 Push를 하면 스택에 1,2,3,4가 저장될 것입니다. 이 때 Push와 동시에 '+'를 출력해야 합니다.

  그러나 Push만 하면 끝나는게 아닙니다. Push와 Pop을 사용해서 4,3,6,8,7,5,2,1의 수열을 만들 수 있는지 검증하는것이 문제의 핵심이기 때문에, 4를 Pop으로 꺼내야 수열의 첫번째 원소를 지정할 수 있습니다. 따라서 Push를 4번 한 뒤 마지막에 Pop을 해서 4를 꺼내며, 이 때 Pop과 동시에 '-'를 출력합니다. 여기까지 처리하면 스택에는 1,2,3이 남아있어야 합니다. 다음으로 3을 입력받으면 Pop으로 3을 꺼내며 '-'를 출력합니다. 이 때 스택에는 1,2가 남아있습니다.

  이제 6을 입력받으면 고민이 생깁니다. Push를 몇번 해야 할까요? 그리고 어떤 수를 Push해야 할까요? 당연히 5,6을 차례로 Push하면 됩니다. 이를 코드로 구현하려면 Push 할 숫자를 카운트하는 변수가 필요할 것입니다. 6까지 Push한다면 '+'는 2개가 출력되고 스택에는 1,2,5,6이 저장됩니다. 그러나 수열을 만드는 것이 목적이기 때문에, 반드시 Pop을 1번 해서 6을 꺼내야 합니다. 따라서 스택의 최종 상태는 1,2,5가 됩니다.

  이제 예제 입력 2를 살펴보겠습니다. 1,2,5까지 입출력 처리를 완료했다면 스택에는 3,4가 남아있을 것입니다. 그러나 그 다음에 3을 입력받으면, 3을 꺼내기 위해 Pop을 2번해서 스택에는 아무것도 남지 않습니다. 이 상태에서 4를 입력받는다면 Push해야 할 숫자는 5이기 때문에 수열 생성이 불가능하게 됩니다. 이를 코드로 구현한다면, Push할 대상이 되는 숫자가 입력받은 숫자보다 클 때 코드를 탈출해야 할 것입니다. 따라서 이 단계에서 NO를 출력하고 프로그램을 종료해야 합니다.

 

코드 구현하기

역시나 없는게 없는 파이썬! 이미 List로 스택 자료구조가 구현되어서 너무 편합니다. 대신 top이 index out of range에 걸리지 않도록 조심해야 합니다.

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    listStack = []
    pushNum = 0
    top = -1
    topStackNum = 0
    str = ""

    for _ in range(n):
        inputNum = int(input())

        while topStackNum != inputNum:
            if pushNum < inputNum:
                pushNum += 1
                topStackNum = pushNum
                top += 1
                str += "+" + "\n"
                listStack.append(pushNum)
            else:
                top -= 1
                if top < 0:
                    if top < -1:
                        break
                    topStackNum = 0
                else:
                    topStackNum = listStack[top]
                str += "-" + "\n"
                listStack.pop()

        if top < -1:
            str = "NO"
            break

        top -= 1
        if top < 0:
            topStackNum = 0
        else:
            topStackNum = listStack[top]
        str += "-" + "\n"
        listStack.pop()

    print(str)

if __name__ == '__main__':
    main()