29_백준 1874번 파이썬 스택수열

일단 이 문제를 이해하는데 한참 걸렸다.

문제 이해 :
8 4 3 6 8 7 5 2 1 n = 8 # 8개의 숫자를 받겠다
4 3 6 8 7 5 2 1 # n이하의 8개의 숫자입력
1-> 2-> 3-> 4 5 6 7 8 순서로 진행하면서 push를 하고 '+'를 기록한다.

입력된 숫자가 나오면 pop을 하고 '-'를 기록한다.

push와 pop을 써서 위의 숫자 리스트를 만들 수 있으면

기록된 '+' 와 '-' 를 한줄 씩 출력한다.

1 -> 2 -> 3 -> 순으로 진행하니까
우선 스택에 push를 먼저 하면 1이 담긴다
stack = [1]
한번 더 push를 하면 2가 담긴다.
stack = [1, 2]
...
이런식으로 push를 4번해주면
stack = [1, 2, 3, 4]
입력받은 수열과 같게 하려면 pop을 두번 해주면
stack = [4, 3]
이런식으로 push와 pop을 해가며 pop을 이용해
입력받은 수열([4, 3, 6, 8, 7, 5, 2, 1])을 만드는 것이다.
문제만 이해한다면 쉽게 풀 수 있었다.

• 풀이

from sys import stdin

n = int(stdin.readline())
stack = []  # 스택
insert_num = 1  # 스택에 넣는 값
result = []  # 결과 리스트
for i in range(n):
    num = int(stdin.readline())

    # num값 까지 스택에 push
    while insert_num <= num:
        stack.append(insert_num)
        result.append('+')
        insert_num += 1

    # 스택 맨 끝값 stack[-1] == num 이면 pop
    if stack[-1] == num:
        stack.pop()
        result.append('-')

    else:  # stack[-1] != num 이면 print('NO')
        print('NO')
        exit(0)  # clean exit without any errors

for i in result:
    print(i)