[그리디] 기출 문제 (3) 무지의 먹방 라이브 ✅

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))
    
    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]