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

기본적으로 모든 경우를 돌면서 계산하면 되지만, 해당 문제는 효율성도 보기에 특정 단위별로 끊어져야겠다는 생각이 들었다.

 

나는 최소 값만큼을 돌리는 단위로 계산이 되야한다고 생각은 하였지만, 해당 부분을 어떻게 처리해야하는지 어려움이 있었다.

찾아보니, 해당 부분은 previous 값을 0으로 시작하여 (heapq의 최소 값과의 차이) * (남은 q 개수)로 k를 줄여가면 된다는 사실을 알 수 있었다.

 

# 무지의 먹방 라이브

import heapq


def solution(food_times, k):
    answer = -1
    food_num = len(food_times)

    h = []
    for i in range(len(food_times)):
        heapq.heappush(h, (food_times[i], i + 1)) # 우선순위 q

    previous = 0 # 이전 값
    while h:
        t = (h[0][0] - previous) * food_num # h[0][0] = 가장 작은 값
        if k >= t:
            k -= t
            previous, _ = heapq.heappop(h)
            food_num -= 1
        else:
            h.sort(key=lambda x: x[1])
            answer = h[k % food_num][1]
            break
    return answer

 

heapq라는 우선순위 큐 자료구조도 많이 사용해보면서 해당 방식이 익숙해질 수 있도록 노력이 필요해보인다..!