[파이썬(python)] 무지의 먹방 라이브

처음엔 deque를 이용해 구현했다.

from collections import deque
def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    
    queue = deque([0])
    
    for i in range(k):
        
        target = queue.popleft()
        food_times[target] -= 1
        
        
        #i번째에 먹을 음식 찾기
        
        target = (target+1) % len(food_times)
        
        for j in range(target, len(food_times)):
            if food_times[j] > 0 :
                queue.append(j)
                break
                
    return queue.popleft() + 1

그러나 효율성 제로..ㅜ 효율성이 o(n2)이라 그런것같다.

 

답지를 보면서 코드를 수정한 결과

 

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))
    
    q.sort(key = lambda x:x[0])
    length = len(food_times)
    min_time = q[0][0] * length
    cnt = 0
    
    while cnt + min_time <= k:
        food = heapq.heappop(q)
        cnt += min_time
        length -= 1
        for i in range(length):
            q[i][0] -= food[0]
        min_time = q[0][0] * length
    
    result = sorted(q, key = lambda x:x[1])
    return result[(k - cnt) % length][1]

 

효율성 테스트에서 하나만 통과했다.

왜지 ??? 아마도 while문 안에서 for문을 다시 사용한 것이 문제인가보다. 그렇다면 for문을 삭제하는 방법을 생각해봐야한다

 

답지를 참고한 결과 어차피 음식의 순서만 중요할 뿐 음식의 다먹는 시간을 계속 변경해줄 필요가 없다.

따라서 직접 음식의 시간을 계속 변경해주는 것보다

뺄 음식을 정확히 구하고 시간을 정확히 카운트해주는 것이 효율성이 훨씬 좋다.

 

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])
    
    q.sort(key = lambda x:x[0])
    length = len(food_times)
    min_time = q[0][0] * length
    cnt = 0
    
    while cnt + min_time <= k:
        food = heapq.heappop(q)
        cnt += min_time
        length -= 1
        min_time = (q[0][0] - food[0]) * length
    
    result = sorted(q, key = lambda x:x[1])
    return result[(k - cnt) % length][1]