백준_1874_스택 수열(Stack)

from sys import stdin

n = int(input())
stack = []
t = 1
result = []
s_list = []
for _ in range(n):
    s_list.append(int(stdin.readline().rstrip()))
for s in s_list:
    if not stack or s > stack[-1]:
        result.append('+')
        for v in range(t, s):
            result.append('+')
            stack.append(v)
        result.append('-')
        t = s + 1
    elif s == stack[-1]:
        stack.pop()
        result.append('-')
    else:
        print('NO')
        break
else:
    for i in result:
        print(i)
    

Stack이 비어있거나 Stack의 마지막 값보다 주어진 수가 크다면 스택에 주어진 수 까지 추가한다음 주어진 수는 바로 pop 함으로써 1부터 주어진 수까지 차례대로 꺼낼 수 있게한다.

Stack에 숫자를 넣을 때는 어차피 마지막 숫자는 바로 pop 하므로 굳이 넣지 않는다.

t 값을 통해 pop하기 전 마지막으로 넣었던 숫자의 정보를 기억해 놓는다.

이때 Stack의 마지막 값보다 주어진 수가 작다면 차례대로 꺼낸게 아니므로 No를 출력한다. 꺼낼 숫자는 반드시 Stack의 마지막 값과 같아야한다.

---

예전에 풀때는 문제 파악을 하지 못해서 풀지 못했던걸로 기억한다.
문제를 파악하는 것도 알고리즘에서 중요한 능력이라는 것을 다시 한번 상기시켜준 문제