[BOJ/Python3] 17298번 오큰수

문제

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

자료구조, 스택

---

Algorithm

A[i] (입력 값) 리스트, NGE 리스트, stack 리스트를 준비
인덱스를 스택으로 만들어서 각 인덱스의 오큰수를 찾아 졸업시키기
졸업하지 못한 인덱스는 stack 리스트에 쌓임, 끝까지 졸업하지 못한다면 NGE 리스트에서 초기값 -1로 표현됨
A[i] 리스트의 현재 비교값(A[i])와 졸업 대상 (A[stack[-1]])을 비교해 현재 비교값이 더 크면 오큰수를 발견한 것
=> 오큰수를 해당 인덱스에 저장하고, 그 인덱스 값은 stack에서 pop되면서 졸업

---

Code

n = int(input())

a_li = list(map(int, input().split()))
NGE = [-1]*n
stack_li = [0]

for i in range(1, n):
    while stack_li and a_li[i] > a_li[stack_li[-1]]:
        NGE[stack_li.pop()] = a_li[i]
    stack_li.append(i)
    
print(*NGE)