[알고리즘] 무지의 먹방 라이브 Python

무지의 먹방 라이브 Python으로 푼 저의 풀이입니다

이 문제는 알고리즘 문제 유형 중에서 구현 유형이라 저는 생각합니다

 

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

 

문제풀이 과정

힙을 이용해서 가장 적게 남은 시간을 하나씩 확인합니다

가장 적게 남은 시간 x 남은 음식 개수 < 네트워크 끊기기 전까지 남은 시간이라면 해당 음식을 먹을 수 있습니다

이렇게 음식을 먹어가면서 현재 주어진 음식을 못 먹게되면

음식번호 순으로 정렬한 뒤에 mod 연산으로 다음에 먹을 음식을 구하는 과정입니다

 

import heapq
from typing import List


def get_next_food(food_times: List[int], k: int):
    # 음식을 다 먹어서 더 먹을 게 없는 경우
    if sum(food_times) <= k:
        return -1

    # 힙 (최소힙) 자료구조를 사용
    # 힙에 (음식시간, 음식번호)를 넣습니다. 음식시간 기준으로 최소힙 정렬이 됩니다.
    h = []
    for i, food_time in enumerate(food_times):
        heapq.heappush(h, (food_time, i + 1))

    # 음식 먹은 총 시간
    total_elapsed_time = 0

    # 현재까지 각 음식을 먹는 데 걸린 최대시간
    # 예를들어 food_times: [1,3,5,9]이고 현재 5까지 진행됐으면 5입니다
    each_eating_time = 0

    length = len(h)  # 음식 개수
    # 최소 음식시간 * 남은 음식들 개수 < 음식을 먹을 수 있는 시간  (현재 음식을 다 먹을 수 있는 조건이 만족됩니다)
    while length * (h[0][0] - each_eating_time) < (k - total_elapsed_time):
        total_elapsed_time += length * (h[0][0] - each_eating_time)
        each_eating_time += (h[0][0] - each_eating_time)

        heapq.heappop(h)
        length -= 1

    # 음식 번호 순으로 정렬하고
    # mod 연산을 이용해서 먹을 음식을 구합니다
    result = sorted(h, key=lambda x: x[1])
    return result[(k - total_elapsed_time) % len(h)][1]

 

알 수 있었던 지식/스킬

[문제풀이 스킬]

- 문제 풀이 내내 최소/최대 값을 이용한다면 heap을 사용합니다

- 1,2,3,1,2,3,1,2,3 이렇게 순환해서 구한다면 mod 연산을 이용하면 됩니다

 

[지식]

- (파이썬 지식) 파이썬에서는 힙은 최소힙만 존재합니다

최대힙을 사용하고 싶으면 negative(-)를 사용하여 최댓값이 최솟값으로 만들어 push하고

pop해서 가지고 와서 다시 -를 붙여 부호를 원래대로 만들어 사용하면 됩니다

import heapq

items = [1, 2, 3]

# [최대힙]
max_heap = []
for item in items:
    # -를 붙여서 최댓값이 최솟값으로 만들어서 넣습니다
    heapq.heappush(max_heap, -item)
print(max_heap)  # [-3, -2, -1]

for _ in range(len(max_heap)):
    element = heapq.heappop(max_heap)
    # -를 붙였던 것을 원래 부호로 다시 돌려줍니다
    print(-element, end=' ')  # 3 2 1