[Python] 백준 #1874 스택 수열

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

1874번: 스택 수열

[ 자료구조 ]

스택

 

[ 접근 방법 ]

나와야하는 target 숫자까지 모두 스택에 push해주고 target 숫자를 pop하여 꺼내준다.

만약 현재 target의 숫자가 이 전의 target 보다 작은 경우, 한번 pop해주었을 때 해당 값이 나오면 계속 진행하고

그렇지 않으면 불가능한 경우이므로 NO를 출력하고 반복문을 빠져나온다.

 

[ 코드 ] O(N) 280ms

from collections import deque
import sys

N = int(sys.stdin.readline().strip())
que = deque()
num = deque([i + 1 for i in range(N)])
finish = []
result = []
check = 0
for i in range(N):
    target = int(sys.stdin.readline().strip())
    if len(finish) != 0 and finish[-1] > target:
        if que.pop() == target:
            result.append('-')
        else:
            print('NO')
            check = -1
            break
    else:
        while True:
            q = num.popleft()
            que.append(q)
            result.append('+')
            if q == target:
                break
        que.pop()
        result.append('-')
        finish.append(target)

if check == 0:
    for i in result:
        print(i)