[백준][Python] 1874번 스택 수열

1874번: 스택 수열

 

코드

 

import sys
n = int(input())
arr = []
ans = []
stack = []
num, no = 0, 0
for i in range(n):
    a = int(sys.stdin.readline())
    arr.append(a)

for i in arr:
    if num < i:
        for j in range(num+1, i+1):
            stack.append(j)
            ans.append("+")
        stack.pop()
        ans.append("-")
        num = i
    else:
        if i == stack[-1]:
            stack.pop()
            ans.append("-")
        else:
            no = -1
            break

if no == -1:
    print("NO")
else:
    for i in ans:
        print(i)

 

설명

 

문제 이해하기 너무 어렵다.. 

스택에 push를 할 때는 1부터 n까지 순차적으로 넣어야 한다. 

n = 8 이고 수열이 [4, 3, 6, 8, 7, 5, 2, 1] 일 때 

먼저 4가 pop 되어야 하므로 스택에는 1,2,3,4가 모두 담겨있어야 된다. 따라서 1부터 4까지 push 해줘야 된다. 

4를 pop 해주면 스택에는 1,2,3이 남아있다. 다음으로 3이 주어졌기 때문에 스택에 있는 3을 pop 해준다. 

그러면 스택에는 1,2가 남아있다. 

위와 같이 push와 pop을 반복하면서 입력된 수열을 만들어주면 된다. 

 

num 변수를 만들어서 만약 수열의 숫자(j)가 num보다 크면 num+1 부터 j까지의 숫자를 스택에 넣어주었고 j는 pop 해주었다. 만약 수열의 숫자(j)가 num보다 작으면 이미 스택에 넣은 숫자이기 때문에 pop을 해주어야한다. 그런데 만약 스택의 마지막 숫자가 j 와 일치하지 않으면 입력된 수열을 만드는 것이 불가능하므로 "NO"를 출력해준다.