무지의 먹방 라이브 파이썬

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

프로그래머스

 

그리디 같기도 하고 꽤 엣지 케이스가 많다. 우선은 주어진 food_times 리스트를 인덱스와 함께 최소 힙에 넣어준다.

 

그렇게 되면 가장 작은 시간의 음식을 바로 꺼낼수있다. 또 dict를 활용해 똑같은 시간의 갯수를 세어주엇다.

 

우선 k와 무관하게 모든 배열은 작은 시간의 음식이 먼저 소진되는 것이 당연하다.

예를들어 k가 충분히 클때 [5,4,2,2,5] 에서 2바퀴를 돌것이다. 그렇게 되면  10초(길이*최소시간)에서는 [3,2,0,0,3]이 되고 맨 앞 음식부터 다시 시작한다.  이런 식으로 k와 가장 작은 아이템들을 지워가면서 구해간다.

 

하지만 위에서 k가 9라면 어떨까? 이는 가장 작은 음식을 못비워내는 경우이다. 그렇다면 모든 음식이 존재하게 되므로 배열의 길이와 나머지 연산을 통해 답을 구하면 된다. 

그렇다면 엣지 케이스는 무엇일까? k가 너무 큰 경우이다. 간단하게 [1]에 k가 5라면 모든 음식의 시간을 계산해도 k보다 작으므로 -1이다. 이럴 경우 모든 계산을 하게 되어 h가 비워지게 된다.

 

import heapq
from collections import defaultdict
def solution(food_times, k):
    h = []
    d = defaultdict(int)
    for idx,t in enumerate(food_times):
        heapq.heappush(h,(t,idx))
        d[t]+=1
    before = 0
    while 0<len(h)<=k :
        left = len(h)
        time,idx = heapq.heappop(h)
        if k>=left*(time-before):
            k += -left*(time-before)
            for i in range(d[time]-1): heapq.heappop(h)
        else:
            heapq.heappush(h,(m,idx))
            break
        before = time
    return sorted(h,key = lambda x:x[1])[k%len(h)][1]+1 if h else -1