[백준 / 17298] 오큰수 - Python

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

17298번: 오큰수

<풀이>

시간 초과를 줄이기 위해서 deque를 사용했더니 통과했다.

 

오른쪽에 있는 큰 수를 찾아야 하므로 뒤에서부터 탐색을 해주었다.

 

<전체 코드>

from collections import deque

N = int(input())
arr = list(map(int, input().split()))
mostBigNum = -1
O_arr = deque()
answer = deque()
for i in arr[::-1]:
    if i >= mostBigNum:
        O_arr = deque([i])
        answer.appendleft(-1)
        mostBigNum = i
    else:
        while True:
            now = O_arr[0]
            if i < now:
                answer.appendleft(O_arr[0])
                O_arr.appendleft(i)
                break
            else:
                O_arr.popleft()

print(' '.join(list(map(str, answer))))