1874번 스택 수열

스택 수열

풀이

현재 스택이 비어있거나 스택의 맨 위 보다 더 큰 수를 출력해야 할 때, 해당 수를 출력하기 위한 유일한 방법은 해당 수가 스택에 넣어질 때까지 계속 수를 넣는 것입니다.

따라서 스택에 계속 넣어도 해당 수를 뽑아낼 수 없다면 주어진 수열은 스택 수열이 아닙니다.

현재 스택의 맨 위와 같은 수를 출력할 수 있는 유일한 방법은 현재 스택의 맨 위를 뽑아내는 것입니다. 이 경우는 항상 가능합니다.

현재 스택의 맨 위 보다 더 작은 수를 출력할 수 있는 방법은 없습니다. 이 경우도 스택 수열이 아닙니다.

조금 일반화해 봅시다.

스택이 비어있거나 스택의 맨 위가 출력해야 할 수와 다르다면 수를 계속 넣습니다. 만약 수를 더 넣어야 하는데 이미 까지 넣어서 더 넣을 수 없다면 스택 수열이 아닙니다.

코드

from collections import deque
 
 
def main():
    n = int(input())
 
    stack = deque()
    i = 1
    history = []
 
    for _ in range(n):
        target = int(input())
 
        while i <= n and (len(stack) == 0 or target != stack[-1]):
            history.append("+")
            stack.append(i)
            i += 1
 
        if len(stack) == 0 or stack[-1] != target:
            print("NO")
            return
 
        history.append("-")
        stack.pop()
 
    print(*history, sep="\n")
 
 
main()