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

문제

백준 1874번 - 스택 수열

해결 과정

• 스택으로 풀기
• current_num이 하나씩 입력 받은 숫자보다 작다면
  • stack.append(current_num)
  • current_num은 1씩 증가
  • answer에push를 의미하는 + 삽입
• stack에 마지막 삽입된 값이 입력 받은 숫자와 같다면
  • stack.pop()
  • answer에pop를 의미하는 - 삽입
• stack에 마지막 삽입된 값이 입력 받은 숫자와 다르다면
  • 수열을 만드는게 불가능하므로 flag = False

시행착오

• 왜 틀렸지? -> 입력 받은 숫자를 바로바로..

import sys
n = int(sys.stdin.readline())

array = []
for _ in range(n):
  array.append(int(sys.stdin.readline()))

i = 2
num = 0
stack = [1]
answer = ['+']
while stack:
  if stack[-1] != array[num]:
    stack.append(i)
    i += 1
    answer.append('+') 
  else:
    stack.pop()
    answer.append('-')
    num += 1  

if num != n:
  print('NO')
else:
  for s in answer:
    print(s)

풀이

import sys
n = int(sys.stdin.readline())

current_num = 1
stack = []
# +,-를 삽입 할 배열
answer = []
# 수열 만드는게 불가능한지 아닌지 확인하는 Flag
flag = True

for _ in range(n):
  x = int(sys.stdin.readline())
  while current_num <= x:
    stack.append(current_num)
    current_num += 1
    answer.append('+')
  if stack[-1] == x:
    stack.pop()
    answer.append('-')
  else:
    flag = False


if not flag:
  print('NO')
else:
  for s in answer:
    print(s)