[프로그래머스] 무지의 먹방라이브 : Greedy
문제
https://programmers.co.kr/learn/courses/30/lessons/42891
풀이
from heapq import *
def solution(ft, k):
new_ft = [(val, idx + 1) for idx, val in enumerate(ft)] # food_time을 순서와 함께 새로 정의
heapify(new_ft) # heap 이진 트리 형태로 갱신
spendTime = 0
prev = 0
l = len(ft) # 남아있는 음식의 가짓수
ans = -1 # k초뒤의 방송사고 뒤 음식을 먹는것이 불가능 할 때 == 모든 음식의 합 시간이 k 보다 작을 때
if sum(ft) > k:
'''현재까지 걸린 전체 시간 + (현재 가장 빨리 먹을 수 있는 음식의 사이클 - 지금까지 거친 사이클 횟수) * 남은 음식 수 <= k
(현재 가장 빨리 먹을 수 있는 음식 시간 - 지금까지 거친 사이클 횟수) * 남은 음식 수
== 현재 가장 빨리 먹을 수 있는 음식은 총 n 사이클이고 그 시간은 n * l 이다.'''
while spendTime + (new_ft[0][0] - prev) * l <= k:
time, idx = heappop(new_ft)
'''처음부터 현재 음식까지 먹는데 걸리는 전체 시간 == 이전까지 걸린 시간 + 현재 음식을 먹는데까지 걸리는 시간'''
spendTime += (time - prev) * l
''' prev == 현재 까지 진행된 사이클의 수. 따라서 현재 음식을 다 먹는데 걸리는 사이클은
(원래 다 먹기까지 걸리는 사이클 - 현재까지 걸린 사이클) 이다. 걸리는 시간(t)은 여기서 전체 음식 수를 곱한다.'''
l -= 1
prev = time
new_ft.sort(key=lambda x: x[1])
ans = new_ft[(k - spendTime) % l][1]
return ans
print(solution([3, 1, 2], 5))
Author And Source
이 문제에 관하여([프로그래머스] 무지의 먹방라이브 : Greedy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seilk/프로그래머스-무지의-먹방라이브-Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)