[자료구조]백준 1874번 스택 수열 with Python

https://www.acmicpc.net/problem/1874
사실 문제이해를 못해서 문제가 뭔말인지 다른 브로그 읽어본건 안비밀ㅎ
오름차순으로 들어간다는게 작은수 -> 큰수로 들어간다라고 이해를 해서 엥 뭐지?했는데
알고 보니 4를 pop하려면 1, 2, 3, 4 이렇게 push를 해야한다 라는 말이었다.
이렇게 스택에 push pop하면서 입력받은 수열을 만들면 성공, 만들지 못하면 NO를 출력하는 문제였다.

import sys

n = int(sys.stdin.readline().rstrip())
stack = []
last = 0
o = ''
for _ in range(n):

    i = int(sys.stdin.readline().rstrip())

    if i not in stack:
        for j in range(last+1, i+1):
            o += '+'
            stack.append(j)
        last = i

    n = stack.pop()
    if n == i:
        o += '-'
    else:
        print('NO')
        last = -1
        break

if last != -1:
    for c in o:
        print(c)

시간초과~ 알아낸 이유는?! 바로 if i not in stack 이부분!!!!
i가 stack에 있는지 처음부터 끝까지 훑으면서 검사하기 때문에 시간이 오래걸린다.
생각해보니까 last로 내가 어디까지 stack에 push했는지 체크하는데 입력받은 숫자가 last보다 작다면 이미 stack에 들어있는 숫자란 뜻이므로
last가 입력받은 숫자보다 작을 때만 stack에 push하게 코드를 고쳤고 성공!!!

import sys

n = int(sys.stdin.readline().rstrip())
stack = []
last = 0
o = ''
for _ in range(n):

    i = int(sys.stdin.readline().rstrip())

    if last < i:
        for j in range(last+1, i+1):
            o += '+'
            stack.append(j)
        last = i

    n = stack.pop()
    if n == i:
        o += '-'
    else:
        print('NO')
        last = -1
        break

if last != -1:
    for c in o:
        print(c)