[프로그래머스] 무지의 먹방 라이브 / 우선순위 큐(힙)

https://programmers.co.kr/learn/courses/30/lessons/42891#

우선순위 큐 문제입니다.

예를 들어 foods_time이 [3, 4, 5, 6, 7, 8, 9, 10] 이라고 해봅시다.

이 정보만 주어졌을 때 가장 작은 값인 3, 그리고 배열의 길이 7 이니

21초 후에는 [1, 2, 3, 4, 5, 6, 7] 이 됨을 알 수 있겠죠?

즉 N초(가장 작은 값 x 배열의 길이)후의 결과를 가장 작은 값, 배열의 길이로 알 수 있는 것입니다.

그리고 가장 작은 값 => 우선순위 큐 임은 알고리즘을 조금 풀어보신 분들은 쉽게 눈치채셨겠죠??

가장 작은 값 x 배열의 길이로 계속 점프를 해줍니다.
그런데 이 값이 이제 K초 후를 넘어가는 경우 멈춰줍니다.
그 때부터는 모듈러 연산을 통해 한 번에 값을 찾을 수 있습니다!

import heapq

def solution(food_times, k):

    if sum(food_times) <= k:
        return -1

    food_times = [ (i, idx+1) for idx, i in enumerate(food_times) ]
    pq = []
    for f, idx in food_times:
        heapq.heappush(pq, (f, idx))

    cnt = 0
    prev = 0

    while cnt + (pq[0][0] - prev) * len(pq) < k:
        n = len(pq)
        if not pq:
            break
        f, idx = heapq.heappop(pq)
        cnt += n * (f - prev)
        prev = f

    q = []
    for f, idx in food_times:
        if f - prev > 0:
            q.append((f - prev, idx)) 
    return q[(k - cnt)%len(q)][1]