[백준] 17298: 오큰수 (python 파이썬)

해당 문제는 다음과 같은 알고리즘으로 풀이했다.

• 결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)
• stack은 아직 자기보다 큰 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.
• 반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하자.)
• stack에 남아있는 원소가 있고(자기보다 큰 수를 찾지 못한 원소가 있고), 그 원소들 중 가장 오른쪽의 원소와 current_value를 비교했을 때 current_value가 더 크다면, stack에서 가장 오른쪽의 원소를 빼내고, 해당 원소의 NGE값은 current_value로 설정한다. 

해당 코드는 다음과 같다.

import sys

input = sys.stdin.readline

n = int(input())
result = [-1 for _ in range(n)]
array = list(map(int, input().split()))
stack = [0]

for i in range(1, n):
    while stack and array[stack[-1]] < array[i]:
        result[stack.pop()] = array[i]
    stack.append(i)
    
print(*result)

---

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