LV 2: 뒤에 있는 큰 수 찾기

문제 링크

LV 2: 뒤에 있는 큰 수 찾기

구현 방식

• 스택으로 구현하려다가 시간초과가 나서 최소힙을 이용하여 구현해주었다

• numbers를 순서대로 순회하면서, 매 회마다 numbers[i]의 값을 heap에 넣어준다

• heap의 가장 작은 원소가 현재 numbers[i]보다 작을 때까지 heappop을 진행하면서, result의 heappop을 통해 나온 index 위치의 값을 numbers[i]로 갱신해준다

코드

import heapq

def solution(numbers):
    N = len(numbers)
    
    heap = [] # [value, index] 형식
    result = [-1] * N
    
    for i in range(N):
        
        while heap and heap[0][0] < numbers[i]:
            value, index = heapq.heappop(heap)
            result[index] = numbers[i]
            
        heapq.heappush(heap, [numbers[i], i])
        
    return result