스택 수열 - 1874번

deque와 heapq를 이용하였다.

1부터 n까지의 수를 만들어줘도 되지만

heapq를 이용하여 만들어져야 하는 수열을 입력받으면서 heapq에 넣으면서

바로바로 정렬을 빠르게 시켰다. (미리 1부터 n을 만들어두는 방식을 썼으면 더 효율적이었을듯함)

 

from collections import deque
import heapq
import sys

h = []
stack = deque()
arr = []
result = deque()
idx = 0
t = int(input())

for _ in range(t):
    inn = int(sys.stdin.readline())
    heapq.heappush(h,inn)
    arr.append(inn)
while h or stack:
    # print(stack)
    if stack and stack[-1] == arr[idx]:
        stack.pop()
        idx += 1
        result.append('-')
        # print('-')
    else:
        inn = heapq.heappop(h)
        stack.append(inn)
        result.append('+')
        # print('+')
    if not h and stack and stack[-1] != arr[idx]:
        result.append('NO')
        print('NO')
        break
if result[-1] != 'NO':
    for i in range(len(result)):
        print(result.popleft())