백준 17298 오큰수

https://www.acmicpc.net/problem/17298
실패이유 : 시간초과

N = int(input())
series = list(map(int, input().split()))
ans = [-1] * N
stack = []

stack.append(0)
for i in range(1, N):
    while stack and series[stack[-1]] < series[i]:
        ans[stack.pop()] = series[i]
    stack.append(i)

print(*ans)

이중 for문 사용시 O(N^2) 시간 복잡도에 의해 시간초과 발생

• 인덱스를 보관하는 stack 을 만들어 문제해결
• 현재 i(인덱스) 에서 오큰수를 구하지 못했을 경우에도 stack에 현재 인덱스 저장
  • 이후 i+N 의 오큰수를 구할 수 있고, 해당 오큰수는 i의 오큰수이기도 하다.
    
    
    

출처 : https://hongcoding.tistory.com/40