[Algorithm] 프로그래머스 무지의 먹방 라이브 | 파이썬 (2019 KAKAO BLIND RECRUITMENT)

※ 42891 무지의 먹방 라이브

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

프로그래머스

문제 해결 TIP

재귀함수와 if, for 문으로 구현하려 했지만 생각보다 까다로운 조건들이 많았다. 우선순위 큐를 활용하여 쉽게 구현할 수 있다. 시간이 적게 걸리는 음식부터 전체 시간 k에서 빼가며 순차적으로 계산해야 한다. 소요 시간과 음식 번호를 같이 저장하고 우선순위를 위해 heapq 모듈을 사용한다.

 

전체 코드

import heapq

def solution(food_times, k):
    # 더 이상 먹을 음식이 없을때
    if sum(food_times)<=k:
        return -1
    else:
        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)
        # q = [(1, 2), (3, 1), (2, 3)]
        # 가장 적게 걸리는 음식부터 빼면서 비교
        while ((q[0][0] - previous)*length) <= k - sum_value:
            now = heapq.heappop(q)[0]
            sum_value += (now - previous)*length
            length -= 1
            previous = now
        result = sorted(q,key=lambda x: x[1])
        # result = 	[(3, 1)]
        return result[(k-sum_value)%length][1] #먹어야 할 음식 번호 출력