BOJ 17298 오큰수

https://www.acmicpc.net/problem/17298
시간 1초, 메모리 512MB
input :

• N (1 ≤ N ≤ 1,000,000)
• 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)

output :

• 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력

조건 :

• Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미

---

BOJ 2493 탑 문제의 반대 방향에서 출발하는 경우와 동일하다.
시작을 n - 1에서부터 0까지 돌아가며, temp 인 스택을 확인 하는 방식으로 진행한다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
temp = [0]
# 마지막에 reverse 해주기
ans = []

for i in range(n - 1, -1, -1):
    num = data[i]
    flag = 0

    while temp:
        compare = temp.pop()

        if num < compare:
            flag = 1
            ans.append(compare)
            temp.append(compare)
            break

    if not flag:
        ans.append(-1)
    temp.append(num)

ans.reverse()
for item in ans:
    print(item, end=" ")