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

문제 링크

프로그래머스

 

 

 

풀이

import heapq


def solution(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보다 작거나 같을 때만 수행한다.

    cur_sum = 0
    before_food_count = 0
    all_food_count = len(q)

    # 지금까지 소모된 시간 + (이제 소모될 시간)이 k보다 작을 때만 해당음식을 여기 반복문에서 한꺼번에 Pass시킬 수 있다.
    while cur_sum + (q[0][0] - before_food_count) * all_food_count <= k:
        now_food = heapq.heappop(q)
        cur_sum += (now_food[0] - before_food_count) * all_food_count
        all_food_count -= 1
        before_food_count = now_food[0]

    # 빠져나왔다는 건 k보다 커지기 때문에 더 이상 전체를 순회하지 못한다는 의미이다.
    result = sorted(q, key=lambda x: x[1])
    return result[(k - cur_sum) % all_food_count][1]

 

이코테 답을 봤는데, 왜 "이제 소모될 시간"을 "(현재 음식의 수 - 전 음식의 수) * 현재 음식 종류의 수"로 계산하는지 이해가 가질 않아 정리해 보았다.

 

Priority Queue에 4, 6, 8 크기의 음식들이 있다고 가정하자.(편의를 위해 아이템 id는 순서대로 1, 2, 3으로 붙였다.)

이해가 안갔던 부분은 현재 큐의 크기 * (현재 음식 수 - 이전 음식 수) 부분이었다.

 

우선 PQ로 처리하는 이유는 해당 음식이 사이클을 돌아서 사라지기 위한 최소 횟수가 "현재 큐의 크기 * 음식 사이즈"이기 때문인데,  이 수가(정확히는 여기까지 누적된 수) k보다 커진다면 음식이 다 소모되기도 전에 시간이 끝난걸 의미하기 때문에, while을 빠져나와서 index로 구해야한다.

 

여기서 4의 크기를 가진 item1을 기준으로 최소 횟수는 위와 같은 계산처럼 12회가 되며, 이말은 즉슨 item1을 모두 소모하기 위해서는 사이클을 4번 돌아야 함을 의미한다. 즉 item1이 모두 소모된 시점에는 다른 아이템들도 item1의 크기만큼 이미 돌게 된 시점이다.

 

따라서 그 다음 item2가 소모되는 시간을 구하기 위해서는 item1에서 소모된 4개를 빼고 나머지 2개를 대상으로 시간을 구하는게 맞다.

 

계산 상 전체 아이템을 모두 사이클을 통해 처리했을 경우, 소요 시간과 전체 아이템 개수가 18로 동일함을 알 수 있다.