17298번 - 오큰수(python3)

문제 링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

이전에 올린 탑 문제와 비슷하게 접근하면 됩니다. 탑 문제와는 반대로 오른쪽에 있는 큰 수 중 가장 왼쪽에 있는 수를 구하는 문제니까 훑는 방향을 반대로 하면 됩니다. 오큰수가 없는 경우에는 -1을 출력해야 하니, 디폴트를 -1로 두고 오큰수가 있는 경우 해당 오큰수의 인덱스를 저장하면 됩니다.

n = int(input())
lst = list(map(int, input().split()))

stack = []
sol = [-1]*n

for idx in range(n):
    while stack and lst[stack[-1]] < lst[idx]:
        sol[stack.pop()] = idx
    stack.append(idx)

sol = [lst[x] if x != -1 else -1 for x in sol]
print(*sol)