from itertools import accumulate
def solution(food_times, k):
n = len(food_times)
food_acc = list(accumulate((f := [0] + sorted(food_times))))
for i in range(1, n+1) :
if food_acc[i] + (n-i)*f[i] > k :
remain_food = [index+1 for index, food in enumerate(food_times) if food >= f[i]]
idx = (k - (food_acc[i-1] + (n-(i-1))*f[i-1])) % (n-(i-1))
return remain_food[idx]
return -1
알고리즘
n : len(food_times) food_times : 원본 음식 리스트 f : food_times 오름차순 정렬한 리스트 food_acc : f의 누적합 t_i : f[i]를 먹는데 걸리는 시간
\(if\,\,food\_acc[i]+(n-i)f[i]\,>\,k\) 라면 무지는
i번째로 큰 음식을 먹던 도중에 정전이 났다는 뜻이다.
i번째로 큰 음식보다 작은 음식들은 모두 먹어치웠고, 남은 음식들은i번째 음식 이상 음식만 남아있다는 뜻.남은음식리스트에서
남은시간 % (n-(i-1))번째 음식부터 먹으면 된다.
(n-(i-1))는 남은 음식 개수,len(남은음식)과 같음남은 시간 = k - (t_1 + t_2 + ... + t_i-1)
from itertools import accumulate
def solution(food_times, k):
n = len(food_times)
food_acc = list(accumulate((f := [0] + sorted(food_times)))) # i를 1부터 시작하게 만들게하기위해 [0] 추가
for i in range(1, n+1) :
if food_acc[i] + (n-i)*f[i] > k :
remain_food = [index+1 for index, food in enumerate(food_times) if food >= f[i]]
idx = (k - (food_acc[i-1] + (n-(i-1))*f[i-1])) % (n-(i-1))
return remain_food[idx]
return -1