[백준/Python] 1874번 - 스택 수열

import sys
input = sys.stdin.readline

n = int(input())

result = []
stack = []

i = 1
for _ in range(n):
  target = int(input())

  if not stack or stack[-1] < target:
    for num in range(i, target + 1):
      stack.append(num)
      result.append('+')
    i = target + 1
  
  if stack[-1] == target:
    stack.pop()
    result.append('-')
  else:
    break

if stack:
  print('NO')
else:
  print(*result, sep='\n')

 

문제에서 하라는 대로 따라가면서 풀면 된다.

그리고 어떤 경우에 수열이 만들어지지 않는지 생각해보자.

stack의 top 숫자가 현재 순서의 수열 숫자 보다 작을 경우는, 숫자를 스택에 더 채워넣어 원하는 숫자로 맞춰주면 되지만,

stack의 top 숫자가 현재 순서의 수열 숫자 보다 클 경우는, pop()을 하는 순간 수열이 깨지고, 숫자를 더 채워넣어도 도움이 없으므로 수열을 완성시킬 수 없다.