[2019 카카오 신입 공채] 무지의 먹방 라이브

import heapq

def solution(food_times, k):

    # 음식 시간의 총 합이 k와 같거나 작으면 
    # 다음으로 먹을 음식이 없는 것이므로 -1 리턴
    if (sum(food_times) <= k) :
        return -1

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

    length = len(food_times) # 남은 음식 개수
    sum_value = 0 # 한 음식을 다 먹기 위해 걸린 시간
    prev = 0 # 이전에 음식을 먹는데 걸린 시간

    # 남은 음식 개수 * (제일 작게 걸리는 음식 시간 - 이전에 먹은 시간) 이 
    # k - (지금까지 먹은 시간) 보다 작거나 같을 때 반복하기
    # -> 한 음식을 다 먹을 수 있으면 반복문 실행
    while (length * (q[0][0] - prev) <= (k - sum_value)):
        # 시간이 가장 작게 걸리는 음식을 pop 하고, now에 저장
        now = heapq.heappop(q)[0]
         # [(한 음식을 먹는데 걸리는 총 시간) - (이전까지 먹은 시간)] * 음식 개수
        sum_value += (now - prev) * length
        length -= 1 # 음식 개수 하나 빼기
        prev = now

    # 남은 음식 중에서 몇 번째 음식인지 확인
    result = sorted(q, key=lambda x: x[1]) # 번호 순대로 오름차순 정렬
    return result[(k - sum_value) % length][1]

 

최소 힙을 이용해서, 먹는데 가장 시간이 작게 걸리는 음식부터 제거해 나가는 방식을 사용한다.

 

예로 food_times 가 3초(1번), 1초(2번), 2초(3번) , k = 5초 일 때를 생각해보자.

 

먼저 가장 시간이 작게 걸리는 2번째 음식을 제거한다고 생각해보자.

2번을 다 먹는데에 1초가 걸린다. 즉, 2번을 다 먹기 위해 1초 * 3개(음식개수, 음식은 순서대로 먹어야 하므로) -> 3초 가 걸린다.

 

다음으로 작게 걸리는 3번 음식을 먹는다고 하자. 3번을 다 먹는데에 2초가 걸리지만 아까 먹은 1초를 빼야한다.

즉, 3번을 다 먹기 위해 (2-1)초 * 2개(음식개수) -> 2초 가 걸린다.

 

다음으로 1번 음식을 먹어야 하는데, 지금까지 음식을 먹는데 걸린 시간은 5초이고, k 도 5초이다.

더 이상 k초까지 음식을 먹을 수 없다.

 

따라서 (k - 지금까지 먹은 시간) % 남은 음식 개수 로 다음에 먹을 음식을 구할 수 있다.

 

 

볼 때마다 또 까먹고 또 까먹게 되는 문제..ㅎㅎㅎㅎ 계속 보고 머리에 넣자...