[백준 / 파이썬] 1874번 스택 수열

n = int(input())
s = []
a = []
f = 0
c = 1

for i in range(n):
    num = int(input())
    while c <= num:
        s.append(c)
        a.append("+")
        c += 1

    if s[-1] == num:
        s.pop()
        a.append("-")
    else:
        print("NO")
        f = 1
        break

if f == 0:
    for i in a:
        print(i)

 

문제에서 스택에 수를 push 할 때 오름차순으로만 push 할 수 있다고 했는데 예를 들어 4를 push 해야 한다면 1~3까지 모두 push 하고 4를 push 할 수 있다

스택을 쌓으면서 pop을 해야 하는데 pop을 한 수들을 나열했을 때 N줄에 걸쳐 입력받을 수열과 같아야 한다

예를 들어 처음 4를 입력받았다면 처음 pop한 숫자가 4가 되어야 하기 때문에 스택에 1~4까지 있어야 한다

그다음 현재 스택에 1~3까지 있는데 3을 입력받았으니 pop으로 빼내기만 하면 되고 그다음은 6이 나와야 하기 때문에 5, 6을 push 해준다

스택에서 pop 할 숫자가 입력한 숫자보다 크다면 문제가 생긴다

3을 입력했는데 스택에 3, 4가 있다면 pop을 했을 때 4가 나오기 때문에 정답과 일치하지 않게 된다

while문을 이용해 입력한 수를 만날 때까지 push 한다

입력한 수를 만나면 while문 탈출

스택의 TOP값이 입력한 숫자와 같으면 pop을 해서 꺼내고 "-"

스택의 TOP이 입력한 수와 같지 않다면 주어진 수열을 만들 수 없기 때문에 NO출력