09-1. 복습

📝문제 : 무지의 먹방 라이브

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

코드💻

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))

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재 음식 시간 + 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

비교 분석📖

분명히 복습까지 했던 문제로 기억하는데 우선순위 큐로 해결하는 것임을 파악하지 못했다. 이상한 방법으로 빙빙 돌려 풀고 있었다. 다른 일들로 알고리즘 공부에 몇 주 소홀했더니 바로 티가 나는 것 같다.. 그리디 알고리즘 관련 문제이다. 문제를 이해하는 것이 역시나 어려웠지만 그래도 우선순위 큐에 대한 코드를 몇 번 작성했어서 그런지 코드를 보고 이해할 수 있었다.