[알고리즘] 무지의 먹방 라이브

[문제] 프로그래머스 무지의 먹방 라이브
https://programmers.co.kr/learn/courses/30/lessons/42891

첫번째로 roop를 돌면서 하나씩 확인하는 방법이 먼저 떠오르지만,
k는 2 x 10^13 이하의 자연수이므로 최대 2 x 10^13번 돌아야 한다.

heapq 자료구조

힙 자료구조는 우선순위 큐이다.
큐는 가장 먼저 삽입된 데이터가 추출되지만 힙은 가장 우선순위가 높은 데이터가 추출된다.
따라서 가장 적은 시간이 걸리는 음식을 먼저 먹기 위해서 힙 자료구조를 이용한다.

문제 해결 hint

1. 가장 시간이 작은 음식부터 (음식시간, 음식 번호) 형태로 우선순위 큐에 삽입
   food_fime에서 k 만큼 이동하다보면 가장 시간이 작은 음식이 0이 된다. 따라서 가장 시간이 작은 음식만큼 다른 food_time 의 수를 빼준다면 roop를 돌리는 수를 줄일 수 있기 때문이다.

2. 가장 시간이 작은 음식을 먹기 위한 시간을 구한다.
   min_time 은 남은 음식의 개수 x 음식을 먹는 시간이다.

3. k를 min_time 만큼 빼준다. 그리고 남은 음식의 개수도 하나씩 줄여준다.

4. 두번째로 시간이 작은 음식을 먹는 시간을 구한다. 마찬가지로 남은 음식의 개수 x 음식을 먹는 시간이다. 이때 다음 먹을 음식의 시간이
   현재 남은 전체 시간보다 크면 빼지 않는다.

5. 그리고 남은 음식을 음식의 번호 기준으로 정렬하고, k 만큼 이동하여 출력한다.

import heapq

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

    # 시간이 작은 음식부터 빼야 하므로 (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i + 1))

    # 가장 적은 시간이 걸리는 음식을 먹기 위한 시간
    min_t = 0
    # 직전까지 사용한 시간
    total_t = 0
    # 남은 음식의 개수
    length = len(food_times)

    # 남은 시간이 다음 먹을 음식의 시간보다 작은 경우 출력
    while min_t <= k:
        # 가장 적은 시간이 걸리는 음식을 뺀다
        min_q = heapq.heappop(q)[0]

        # 가장 적은 시간이 걸리는 음식을 먹는 시간을 구한다
        min_t = length * min_q

        # 남은 시간, 음식의 개수
        k = k - min_t
        length -= 1

    # 남은 음식을 음식의 번호 기준으로 정렬한다
    result = sorted(q, key =lambda x: x[1])
    print(result[k % length][1])