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

문제

문제링크

1부터 n까지 순서대로 스택에 넣었다가 빼서 수열을 만들 것이다.

임의의 수열이 주어졌을 때 어떤 순서로 push(+)와 pop(-) 연산을 수행해야 하는 구하라.

 

풀이

수열의 i번째 수보다 current가 작을 때까지 stack에 수를 넣고 push_pop에 push했다는 의미로 '+'를 넣는다.

stack이 비지 않았고 수열의 i번째 수가 stack의 마지막 요소일 때 그 요소를 삭제하고 push_pop에 '-'를 넣는다.

이 경우 삭제한 요소는 새로 만들 임의의 수열의 요소로 들어가지만 연산 순서를 구하는 문제이기 때문에 새 수열은 만들지 않았다.

이외의 경우, 즉 수열을 만들 수 없으면 'NO'를 출력하고 종료한다.

수열이 완전히 만들어졌을 경우 for-else문의 else문이 실행된다. 

push_pop의 요소를 한 줄에 하나씩 출력한다.

 

코드

import sys
input=sys.stdin.readline

n=int(input())
sequence=[int(input()) for _ in range(n)]
stack=[]
push_pop=[]
current=1

for i in range(n):
    while current<=sequence[i]:
        stack.append(current)
        push_pop.append('+')
        current+=1

    if stack and sequence[i]==stack[-1]:
            stack.pop()
            push_pop.append('-')
    else:
        print('NO')
        break
else:
    print(*push_pop, sep='\n')