[그리디 문제] 무지의 먹방 라이브

https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

 

<아이디어>

시간이 적게 걸리는 음식부터 확인해나가야 하는 그리디 문제이다.

왜냐하면 번호 순으로 음식을 먹는다고 하더라도 시간이 가장 적게 걸리는 음식은 먹는 순서에서 가장먼저 빠지기 때문이다.

만약 음식번호 순서대로 8초, 6초, 4초가 걸린다고 하고 장애는 15초에 걸리다고 하면,

4초가 걸리는 3번은 12초째에 다 먹는다. 그러면 남은 3초 동안에는 1번과 2번만 먹으면 된다

 

이러한 아이디어로 알고리즘은 짜면 다음과 같다

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)) #(음식시간, 번호)를 튜플 형태로 큐에 삽입
        
    sum_value=0 #먹기 위해 사용한 시간
    previous=0 #직전에 다 먹은 시간
    length = len(food_times) #남은 음식의 갯수
    
    #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]) #음식 번호로 q를 정렬
    answer = result[(k-sum_value)%length][1]
    return answer