[프로그래머스] Lv4 무지의 먹방 라이브 | Python

 

프로그래머스

 

먹는 시간이 적은 순으로 정렬해서 (먹는 시간 - 전 음식 먹는 시간) * (음식 개수) 로 k에 천천히 빼주는 식으로 접근했다.  그러다보니 k==0 일 때 k<0일 때 생각해야 할 분기점이 많았다. 뭐는 맞고 뭐는 틀려서 도대체 어디서 잘못 푼 건지 모르겠어서 힌트를 얻어보니... Heap을 사용하라고 한다... 

 

Heap에서 하나씩 pop 하며 K보다 큰지 작은지 계산하는 알고리즘

 

최대/최소를 확인하는 그리디 알고리즘은 Heap을 사용할 생각을 해보자. 그리디 너무 어렵다😂

 

import heapq as hq

def solution(food_times, k):
    heap=[]
    for i,v in enumerate(food_times):
        hq.heappush(heap, (v,i+1))

    prev=0
    answer=-1
    while heap:
        size=len(heap)
        tmp=size*(heap[0][0]-prev)
        
        if k>=tmp:
            k-=tmp
            prev=hq.heappop(heap)[0]
            size-=1
        else:
            idx=k%size
            heap.sort(key= lambda a:a[1])
            answer=heap[idx][1]
            break

    return answer