[백준] 1874번 스택수열(python)

1. 문제

https://www.acmicpc.net/problem/1874

2. 풀이

• 현재 위치인 temp 를 포함해 스택과 반복횟수 그리고 출력값을 저장할 배열등을 입력
• 반복문 안에서 추출할 수를 입력
• 제일 처음에 스택에는 값이 없으므로 1부터 값까지 입력
  - 다음에 만약 스택이 없으면 다시 1부터 저장할 수는 없으므로 세이브 역할을 temp가 해줌
• temp 보다 작은 수가 number라면 무시 (temp는 이전에 최대값으로 자동 저장임)
• 이후 조건 검사 시작
  - 만약 뽑을 값이랑 pop할 위치인 맨 뒤에 값이 같다면 출력하고 - 값 저장
  • 꺼낼수 없는 값이라면 break
• 중간에 멈추었다면 스택이 전부 비워지지 않았을 것이므로 크기가 0이 아니라면 'NO'를 출력
• 아니라면 배열에 담아놧던 기호들을 출력함

3. 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
st = deque()
arr = []
temp = 1

for _ in range(n):
    number = int(sys.stdin.readline())
    while temp <= number:
        st.append(temp)
        arr.append('+')
        temp += 1

    if number == st[-1]:
        st.pop()
        arr.append('-')

    elif number != st[-1]:
        break

if len(st) != 0:
    print('NO')
else:
    print('\n'.join(arr))

시간초과 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
st = deque()
arr = []
temp = 1

for _ in range(n):
    number = int(sys.stdin.readline())
    for i in range(1, number + 1):
        if temp <= i:
            st.append(i)
            arr.append('+')
            temp += 1

    if number == st[-1]:
        st.pop()
        arr.append('-')

    elif number not in st:
        break

if len(st) != 0:
    print('NO')
else:
    print('\n'.join(arr))```