V1 : 단순 풀이

문제에서 요구하는 대로 직접 k만큼 반복하면서 각 음식의 시간을 1씩 줄임

# 단순반복 풀이 - TC20 실패, 효율성 테스트 시간초과
def solution(food_times, k):
	answer = 0
    idx = 0
    n = len(food_times)
    
    while k > 0:
        if food_times[idx] > 0:
            food_times[idx] -= 1
            k -= 1
        
        idx = (idx + 1) % n

    empty = food_times.count(0)
    if empty == n:
        return -1
    
    while food_times[idx] == 0:
        idx = (idx + 1) % n
    
    return idx + 1     

• 문제점 : 효율성 테스트에서 k의 범위가 2 * 10^13으로 매우 크기 때문에 k + a만큼 반복하는데 시간이 너무 오래걸림. 또한 반복을 마치고 idx가 가리키는 값이 0일때 그 다음으로 남은 음식을 찾는데 최대 n만큼의 시간이 소모됨

V2 : 그리디

우선순위 큐를 사용하여 시간이 가장 적게 남은 음식부터 차례대로 먹음
(음식을 먹는 시간 * 남은 음식의 개수)만큼 k를 감소시키기 때문에 k가 빠르게 줄어든다

# 그리디(우선순위 큐) - TC16, 19, 23 실패

def solution(food_times, k):
    heap = []
    
    for i, t in enumerate(food_times):
        heapq.heappush(heap, (t, i + 1))
    
    spend = 0
    n = len(heap)
    while k > 0:
        if n == 0:
            return -1
        
        time, idx = heapq.heappop(heap)
        time -= spend
        
        if n * time <= k:
            k -= (n * time)
            spend += time
            n -= 1
        else:
            heapq.heappush(heap, (time, idx))
            break
        
    
    heap.sort(key=lambda x:x[1])
    return heap[k % n][1]

• 문제점 : 힙에 남아있는 음식의 개수로 모든 음식을 먹을 수 있는지 판단하기 때문에 경우의 수가 제대로 고려되지 않음.
• ce) food_times = [1,1,1,1], k = 4일 때, if n == 0은 통과하고 if n * time <= k문이 실행된 후 while k > 0을 통과하지 못하기 때문에 [0,1,1,1]의 상태로 결과가 반환된다

V3 : 그리디(검증 로직 추가)

V2의 코드에서 -1이 나오는 케이스를 검증하는 로직을 추가함
주어진 시간 k가 전체 음식을 먹는 데 걸리는 시간보다 크거나 같으면 모든 음식을 다 먹을 수 있는 것이므로 -1을 반환

# 그리디(검증 로직 추가) - 성공

def solution(food_times, k):
	if k >= sum(food_times):
    	return -1
        
    heap = []
    
    for i, t in enumerate(food_times):
        heapq.heappush(heap, (t, i + 1))
    
    spend = 0
    n = len(heap)
    while k > 0:
        if n == 0:
            return -1
        
        time, idx = heapq.heappop(heap)
        time -= spend
        
        if n * time <= k:
            k -= (n * time)
            spend += time
            n -= 1
        else:
            heapq.heappush(heap, (time, idx))
            break
        
    
    heap.sort(key=lambda x:x[1])
    return heap[k % n][1]

ANS

# 출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    
    heap = []
    for i, t in enumerate(food_times):
        heapq.heappush(heap, (t, i + 1))
    
    spend = 0
    prev = 0
    n = len(heap)
    
    while spend + ((heap[0][0] - prev) * n) <= k:
        time = heapq.heappop(heap)[0]
        spend += (time - prev) * n
        n -= 1
        prev = time
    
    heap.sort(key = lambda x: x[1])
    return heap[(k - spend) % n][1]

• 2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브