[알고리즘] 무지의 먹방 라이브
[문제] 프로그래머스 무지의 먹방 라이브
https://programmers.co.kr/learn/courses/30/lessons/42891
첫번째로 roop를 돌면서 하나씩 확인하는 방법이 먼저 떠오르지만,
k는 2 x 10^13 이하의 자연수이므로 최대 2 x 10^13번 돌아야 한다.
heapq 자료구조
힙 자료구조는 우선순위 큐이다.
큐는 가장 먼저 삽입된 데이터가 추출되지만 힙은 가장 우선순위가 높은 데이터가 추출된다.
따라서 가장 적은 시간이 걸리는 음식을 먼저 먹기 위해서 힙 자료구조를 이용한다.
문제 해결 hint
-
가장 시간이 작은 음식부터 (음식시간, 음식 번호) 형태로 우선순위 큐에 삽입
food_fime에서 k 만큼 이동하다보면 가장 시간이 작은 음식이 0이 된다. 따라서 가장 시간이 작은 음식만큼 다른 food_time 의 수를 빼준다면 roop를 돌리는 수를 줄일 수 있기 때문이다. -
가장 시간이 작은 음식을 먹기 위한 시간을 구한다.
min_time
은 남은 음식의 개수 x 음식을 먹는 시간이다. -
k를 min_time 만큼 빼준다. 그리고 남은 음식의 개수도 하나씩 줄여준다.
-
두번째로 시간이 작은 음식을 먹는 시간을 구한다. 마찬가지로 남은 음식의 개수 x 음식을 먹는 시간이다. 이때 다음 먹을 음식의 시간이
현재 남은 전체 시간보다 크면 빼지 않는다. -
그리고 남은 음식을 음식의 번호 기준으로 정렬하고, k 만큼 이동하여 출력한다.
import heapq
def solution(food_times, k):
if sum(food_times) <= k:
return -1
# 시간이 작은 음식부터 빼야 하므로 (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
q = []
for i in range(len(food_times)):
heapq.heappush(q, (food_times[i], i + 1))
# 가장 적은 시간이 걸리는 음식을 먹기 위한 시간
min_t = 0
# 직전까지 사용한 시간
total_t = 0
# 남은 음식의 개수
length = len(food_times)
# 남은 시간이 다음 먹을 음식의 시간보다 작은 경우 출력
while min_t <= k:
# 가장 적은 시간이 걸리는 음식을 뺀다
min_q = heapq.heappop(q)[0]
# 가장 적은 시간이 걸리는 음식을 먹는 시간을 구한다
min_t = length * min_q
# 남은 시간, 음식의 개수
k = k - min_t
length -= 1
# 남은 음식을 음식의 번호 기준으로 정렬한다
result = sorted(q, key =lambda x: x[1])
print(result[k % length][1])
Author And Source
이 문제에 관하여([알고리즘] 무지의 먹방 라이브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yj-leee/무지의-먹방-라이브저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)