[백준 17298] 오큰수 (python)

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

문제이해

A[i]의 오큰수는 오른쪽에 있으면서 A[i]보다 큰 수 중에서 가장 왼쪽에 있는 수 없다면 -1을 내뱉는다

문제 포인트

1. -1이 N개만큼 존재하는 배열로 answer을 초기화
2. stack을 선언하고 해당 stack에는 오큰수 이전 요소들의 index와 height를 삽입한다
3. stack의 마지막 요소의 높이보다 현재의 높이가 더 높다면 while문을 순회하며 자신보다 낮은 모든 수를 pop
   3-1. pop한 요소의 index의 현재 height를 삽입해주면 완료

제출한 코드

import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * N
stk = []

for item in enumerate(A):
    index, height = item
    if stk:
        while stk and height > stk[-1][1]:
            current_index, _ = stk.pop()
            answer[current_index] = height

        else:
            stk.append((index, height))
    else:
        stk.append((index, height))

print(*answer)