[백준 1874] 스택 수열 with Python

문제 링크

www.acmicpc.net/problem/1874

1874번: 스택 수열

풀이

import sys

n = int(sys.stdin.readline())
seq = [int(sys.stdin.readline()) for _ in range(n)]
stack = []
plus_minus = []
maximum = 0
is_impossible = False

for num in seq:
    if maximum < num:
        while maximum < num:
            maximum += 1
            stack.append(maximum)
            plus_minus.append("+")
    if stack.pop() == num:
        plus_minus.append("-")
    else:
        is_impossible = True
        break

if is_impossible: print("NO")
else: print("\n".join(plus_minus))

입력된 수열을 seq에 저장한다. 지금까지 push한 횟수를 maximum에 저장하여, maximum보다 큰 수가 나오면 maximum+1부터 그 수에 도달할 때까지 push를 하여 스택을 채운다. 그리고 나서 pop을 진행하는데, 이 때 pop한 수와 num이 같지 않으면 스택으로 구현이 불가능한 수열이므로, 반복문을 탈출하고 "NO"를 출력한다.