무지의 먹방 라이브

💻 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3

📖 문제 해결
먹는 데 소요 시간이 적은 음식 같은 경우 먼저 없어지는 것을 이용하여 해결한 풀이입니다. 우선순위 큐를 이용하면 먹는 데 드는 소요 시간을 기준으로 리스트를 정렬할 수 있고, 적은 시간이 드는 음식이면 맨 앞에 정렬되므로 가능한 한 시간 안에 다 먹을 수 있는 음식들을 미리 없애면 적은 계산량으로 네트워크가 끊긴 이후 먹어야 하는 음식을 찾을 수 있습니다.

# 해설 출처 : 이것이 취업을 위한 코딩테스트다 with python

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))
        
    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수
    
    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k를 비교
    
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length 
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정
        
    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key =lambda x: x[1]) # 음식의 번호 기준으로 정렬 
    return result[(k - sum_value) % length][1]