[백준] 1874 | 스택 수열 [파이썬/python]

문제

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

1부터 n까지의 숫자를 스택에 push, pop할 때 주어진 수열이 만들어질 수 있는지를 확인하는 문제이다.

 

접근

오름차순으로 숫자를 스택에 push하면서, 입력받은 수열의 j번째 인덱스와 값이 같으면 pop하고, j를 증가시킨다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
ans = []

i, j = 0, 0
while i < n:
    i += 1
    b.append(i)
    ans.append('+')
    
    while b and b[-1] == a[j]:
        b.pop()
        ans.append('-')
        j += 1

print('NO' if b else '\n'.join(ans))