무지의 먹방 라이브

문제

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

접근방식

리스트의 요소를 일일이 순회하면서 돌자니 정확성 테스트는 통과할 수 있어도 효율성 테스트는 절대로 통과할 수 없을 거 같았다. 다른 접근 방식을 생각해보다가 결국 풀이 참고했는데 결과적으로 보면 힙을 활용한 그리디 유형의 문제다.

가장 중요한 포인트는 작은 원소 순으로 처리를 한다는 것인데, 이를 위해 (음식 시간, 음식 번호)를 최소 힙에 넣는다. 힙에서 이를 꺼내 가면서 k와 남은 음식 개수*먹는 시간을 비교하여 k에서 빼는 작업을 계속한다. 더 이상 뺄 수 없으면 모듈러를 활용해 다음 먹을 음식 번호를 구한다.

이때, 먹는 시간은 (현재 음식 시간 - 이전 음식 시간)이라는 점을 놓치지 말자

코드

from heapq import heappush, heappop

def solution(food_times, k):
    if sum(food_times) <= k: #edge case
        return -1
    heap = []
    for num, time in enumerate(food_times):
        heappush(heap, (time, num + 1))
    prev_time = 0
    while heap:
        cur_time, num = heap[0]
        time_taken = len(heap) * (cur_time - prev_time) #남은 음식 개수*걸린 시간
        if k >= time_taken:
            k -= time_taken
            heappop(heap)
            prev_time = cur_time
        else:
            break
    if heap: 
        food_nums = list(map(lambda x:x[1], heap))
        food_nums.sort()
        return food_nums[k % len(food_nums)]
    else:
        return -1