[PRO] 무지의 먹방 라이브

우선순위 큐로 접근해야하는 문제이다. 최소인 시간이 걸리는 음식을 찾는 로직을 리스트를 이용하면 $O(N)$인데 우선순위 큐를 이용하면 $O(logN)$이 된다.

import heapq

def solution(food_times, k):
    if sum(food_times) <= k: # 같아도 k초 이후에 먹을거없다.
        return -1
    
    pq = [] # min heap(걸리는 시간 기준)
    for idx, time in enumerate(food_times):
        heapq.heappush(pq, (time, idx+1))
     
    food_len = len(food_times) # 남은 음식수
    time_sum = 0 # 소요한 시간
    previous = 0

    while time_sum + ((pq[0][0]-previous)*food_len) <= k:
        now, food_num = heapq.heappop(pq)
        time_sum += (now-previous)*food_len
        food_len -= 1
        previous = now
    
    pq.sort(key = lambda x: x[1])    
    return pq[(k-time_sum)%food_len][1]