[백준] 17298번 오큰수 (python)

1. 문제

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

2. 풀이

리스트 만큼 반복시킨 스택에 top값(이전 수부터~)에 해당하는 수와 현재 수를 비교 포함한다면 다음으로 넘어가야하기 때문에 스택(인덱스)에서 제거(이미 사용했으므로), 값 대입
아닌 경우 스택이 비어있는 거나 작은 수를 못찾은 상태이므로 스택에 값 추가

3. 코드

import sys

n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
ans = [-1] * n
# 인덱스 저장
st = []

for i in range(n):
    while st and numbers[st[-1]] < numbers[i]:
        index = st.pop()
        ans[index] = numbers[i]
    st.append(i)

print(*ans)

시간초과 코드 - O(n^2)

import sys
from collections import deque

n = int(sys.stdin.readline())
lists = deque(list(map(int, sys.stdin.readline().split())))

temp = lists.popleft()
while lists:
    for i in lists:
        if temp < i:
            print(i, end=" ")
            break
    else:
        print(-1, end=" ")
    temp = lists.popleft()
print(-1)