2021-07-25 @이영훈
무지의 먹방 라이브 Python으로 푼 저의 풀이입니다
이 문제는 알고리즘 문제 유형 중에서 구현 유형이라 저는 생각합니다
문제풀이 과정
힙을 이용해서 가장 적게 남은 시간을 하나씩 확인합니다
가장 적게 남은 시간 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]
Python
복사
알 수 있었던 지식/스킬
[문제풀이 스킬]
•
문제 풀이 내내 최소/최대 값을 이용한다면 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
Python
복사