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

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

n개의 수가 주어질 때 수들을 스택에 오름차순으로 push한 뒤, pop하면서 주어진 수열을 만들수 있는지를 묻는 문제이다.

예를 들어 입력으로 [ 4 3 6 8 7 5 2 1 ]이 주어지면
오름차순으로 정렬했을 때는 [ 1 2 3 4 5 6 7 8 ]이 된다. 이를 차례대로 스택에 push하면서 [ 4 3 6 8 7 5 2 1 ]의 순서로 pop할 수 있어야 한다.

1 2 3 4 push
4 3 pop
1 2 (5 6) push
4 3 6 pop
1 2 5 (7 8) push
4 3 6 8 7 5 2 1 pop

소스코드

---

import sys

n = int(sys.stdin.readline())
num_list = []
for i in range(n):
    num_list.append(int(sys.stdin.readline()))
sorted_list = num_list.copy()
sorted_list.sort()

stack = []
idx = 0
result = ""

for i in sorted_list:
    stack.append(i)
    result += "+\n"
    while (len(stack) > 0 and idx < n) and (stack[len(stack)-1] == num_list[idx]) :
        stack.pop()
        result += "-\n"
        idx += 1
        
if len(stack) != 0:
    print("NO")
else: 
    print(result[:-1])