[Algorithm] 1일1솔 - 백준 1874 스택 수열 (python3)

문제링크

1874번: 스택 수열

 

문제설명

push, pop 을 해가며 pop을 이용해 입력 받은 수열을 만드는 문제이다.

문제의 예시를 살펴보자.

8 4 3 6 8 7 5 2 1 과 같이 입력을 받을 때, 수열 리스트 = [4,3,6,8,7,5,2,1] 이 된다.

우선 push를 4번 하면 스택에 다음과 같이 수가 담긴다.

s = [1,2,3,4]

여기서 입력 받은 수열과 같게 하려면 pop을 두 번 해서 수열 리스트에 담아주면 [4,3] 과 같이 된다.

 

문제풀이

import sys
input = sys.stdin.readline

n = int(input()); stack = []
seq = []; cnt = 1
tmp = True

for i in range(n):
    num = int(input())
    while cnt <= num:
        if cnt > num:
            break
        stack.append(cnt)
        seq.append('+')
        cnt += 1
    if stack[-1] == num:
        stack.pop()
        seq.append('-')
    else:
        tmp = False
if tmp == False:
    print('NO')
else:
    for x in seq:
        print(x)