[백준 파이썬 17298번]오큰수★시간초과★VER2.0★

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

17298번: 오큰수

VERSION 2.0

import sys

from collections import deque

N = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split(' ')))

res = [-1] * N
deque = deque()
deque.append(0)
for i in range(1, N):
    while deque and A[deque[-1]] < A[i]:
        res[deque.pop()] = A[i] #i값은 가만히 있고, deque값은 pop 되므로 작은 것들만 값을 바꿔준다.

    deque.append(i)

for i in res:
    print(i , end = ' ')
#%%

==> deque값을 인덱스화 하여 처리한다.

==> 결과값을 미리 -1로 추가한다.

 

VERSION 1.0

 

import sys
from collections import deque

N = int(sys.stdin.readline())

A = list(map(int , sys.stdin.readline().split(' ')))
B = deque()
for i in enumerate(A):
    B.append(i)
res = [-1] * N
for k ,v in B:
    p = k+1
    # print(k)
    # print(f' B[p][1] : {B[p][1]}')
    while p<=N-1:
        if B[k][1] <= B[p][1]:
            res[k] = B[p][1]
            break
        else:
            p+=1
for i in res:
    print(i , end = ' ')
#%%

==> while 문에 p<=N-1 해놓기 ==> 시간초과 난다.