파이썬) 백준 알고리즘 | 17298번 : 오큰수

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

17298번: 오큰수

백준 17298 '오큰수' 문제입니다.

그냥 구현하면 시간초과가 나는 문제입니다.

dp = [-1] * n 배열을 만들어놓고 for문을 돌립니다.

nums[i] < nums[i+1] 인 경우에는 dp[i] = nums[i+1]로 놓고,

stack에 담긴 인덱스마다 조사를 해줍니다.

else의 경우에는 stack.append(i), stack에 인덱스를 append해줍니다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [-1] * n
stack = deque([])
for i in range(n-1):
    if nums[i] < nums[i+1]:
        dp[i] = nums[i+1]
        while stack and nums[stack[-1]] < nums[i+1]:
            dp[stack[-1]] = nums[i+1]
            stack.pop()
    else:
        stack.append(i)
print(*dp)