백준 #17298 - 오큰수 python

stack은 index가 저장됨

seq에 저장된 숫자끼리 비교하면서 옆 숫자가 크면 ans에 넣고 index도 바뀜

• 무턱대고 배열 내 숫자 전체를 다 비교하면 시간 초과 발생하기 때문에 비교를 해야 하는 경우에만 루프를 돌도록 해야 한다.
  

import sys
N = int(sys.stdin.readline()) 
seq = list(map(int, sys.stdin.readline().split()))
stack = []
ans = [-1 for _ in range(N)] 
stack.append(0) 
i = 1 
while stack and i < N: 
    while stack and seq[stack[-1]] < seq[i]: 
        ans[stack[-1]] = seq[i] 
        stack.pop() 
    stack.append(i) 
    i += 1 

for i in range(N): 
    print(ans[i], end = " ")