✅이코테 - 무지의 먹방 라이브 (그리디)

#1. 문제 설계 및 풀이

그냥 for문 돌려서 배열을 업데이트하며 풀려고했지만 효율성 테스트를 보니 불가능했다.
그리디문제라서 어떻게하면 최선의 선택을 할 수 있을까 고민해봤지만 아이디어가 떠오르지 않았다.

#2. 배운 점 및 개선할 점

해설을 보니 음식 시간 배열에서 시간이 작은 순서대로 빼는 것이 이 문제의 핵심 아이디어였다.
또한, 더이상 음식을 제외할 수 없을때 나머지연산을 통해서 다음 먹어야할 음식을 찾아낼 수 있었다.

그리디 유형에 익숙해지는 연습을 더 해야할 것 같다... 🥲

 

import heapq

food_times = [3, 1 ,2]
k = 5

def solution(food_times, k) :
    total_time = 0
    previous = 0
    food_length = len(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))
        
    # 큐에 음식이 없어질때까지 반복
    # k초 전에 현재 음식 하나를 다 먹을 수 있으면
    while total_time + food_length * (q[0][0]-previous) <= k :
        food_time= heapq.heappop(q)[0]
        
        total_time += food_length * (food_time-previous)
        
        food_length -= 1 # 먹은 음식 제외
        previous = food_time # 이전에 먹은 음식 시간
    
    # k초 전에 현재 음식 하나를 다 먹을 수 없으면
    # 음식을 시간순으로 정렬
    result = sorted(q, key=lambda x : x[1])
    return (result[(k-total_time) % food_length][1])

    
print(solution (food_times, k))