(Python) 백준 1874번 - 스택 수열

문제 링크 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

풀이

deque를 stack으로 사용하여, 입력으로 들어오는 수열을 만들기 위해 발생할 수 있는 모든 경우를 생각하며 하나씩 구현하였다. 

import sys
from collections import deque

n = int(sys.stdin.readline())
stack = deque() # 입력 받은 수들을 저장할 deque
printdeq = deque() # 출력할 '+', '-'를 저장할 deque
top = 0 # 저장한 최대 수가 무엇이었는지 기억할 변수
can = True # 수열이 가능한지 여부
for i in range(n):
    num = int(sys.stdin.readline()) # 수열을 이루는 수들 입력 받기
    try:
        if stack and stack[len(stack)-1] == num: # stack에 값이 들어있고, stack의 맨 위 값과 num이 같다면
            stack.pop() # 맨 위 값 pop
            printdeq.append('-') # '-' 출력 버퍼에 저장
        elif top > num: # 저장한 최대 수가 num보다 크다면
            for _ in range(top-num): # 두 수의 차만큼
                stack.pop() # pop
                printdeq.append('-') # '-' 출력 버퍼에 저장
        else:
            while top < num: # 저장한 최대 수가 num보다 작다면
                top += 1 # 저장한 최대 수가 num가 될 때까지
                stack.append(top) # append
                printdeq.append('+') # '+' 출력 버퍼에 저장
            stack.pop()
            printdeq.append('-') # '-' 출력 버퍼에 저장
    except IndexError: # IndexError가 발생하면
        can = False # 불가능한 수열
        pass
if can == False:
    print("NO")
else:
    for i in printdeq:
        print(i)