[백준] 17028번 오큰수 (Python)

백준 17028 오큰수

오른쪽에 있는 수 중에서 더 큰 수를 출력하고 업다면 -1을 출력해야 한다. 처음엔 dict 자료형에 아직 짝을 찾지 못한 값들을 저장하고 현재 인덱스보다 작다면 해당하는 인덱스의 결괏값을 업데이트하는 식으로 진행했지만.
RuntimeError: * during iteration” in python 에러가 났고. dict.items()을 for 문으로 도는 동안 dict를 편집하면 나오는 에러라는 것을 알게 되었다. 이러한 에러를 해결하기 위해서 dict.copy()를 활용하면 된다는 것을 알게 되었다.

for idx, candidate in candidates.copy().items()

하지만 시간 초과가 났고. 조금 더 알고리즘을 다듬은 끝에 통과할 수 있었다.

1. 현재 숫자가 이전 숫자보다 커야 탐색을 진행한다. (이전 숫자보다 작다면 업데이트할 수 있는 숫자가 없다.)
2. dict가 아닌 heap 구조를 활용하여 탐색을 더 빠르게 종료할 수 있도록 한다.

import sys
import heapq

input = sys.stdin.readline
n = int(input().strip())
nList = list(map(int, input().split()))
heap = []
res = [-1 for _ in range(n)]
heapq.heappush(heap, (nList[0], 0))

for i in range(1, n):
    if nList[i - 1] < nList[i]:
        while heap:
            num, idx = heap[0]
            if num < nList[i]:
                res[idx] = nList[i]
                heapq.heappop(heap)
            else:
                break
    heapq.heappush(heap, (nList[i], i))

print(*res)