[카카오] 무지의 먹방 라이브 python

 

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))
    
    sum_value = 0 # 먹기 위해 사용한 시간 
    pre = 0 # 직전에 다 먹은 음식 시간 
    length = len(food_times) # 남은 음식 개수 
    
    while sum_value + (q[0][0] - pre)*length <= k:
        now = heapq.heappop(q)[0] # 음식 시간
        sum_value += (now - pre) * length
        length -= 1
        pre = now
        
    # 남은 음식 중에서 몇번쨰 음식인지 확인하여 출력
    result = sorted(q, key = lambda x: x[1]) # 음식의 번호 기준으로 정렬하가ㅣ 
    
    return result[(k - sum_value)%length][1]

https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

 

그리디 유형의 문제이다 

k 초후 어떤음식을 먹을 차례인지 알아내는 문제인데, k 초후에 먹고 없어지는 음식들을 제외시키면 좀 더 효율적으로 답을 알 수 있다.

즉, 먹는데 걸리는 시간이 최소인 음식부터 제거해 나간다는 점에서 greedy 스럽다 그리고 이 부분은 파이썬에서 최소 힙을 구현해서 가장 작은걸 빨리빨리 구해낼 수 있다. 이 경우 우선순위 큐 라이브러리인 heapq를 사용할 수 있다 

(난 처음에 for문을 돌려서 0~1초일떄 , 1~2초일떄 하나씩 확인하려고 했는데 효율성에서 꽝이다.. ㅠㅠ)

우선순위 큐에 튜플 형태로 (먹는데 걸리는 시간, 음식번호) 를 넣어 적게 걸리는 시간 순으로 정렬한다.

 

예를 들어 [3, 1, 2] 이 food_times로 주어지면 우선 순위 큐의 내부는 다음과 같을 것이다.

 

현재 가장 시간이 적게 걸리는 음식인 2번 음식은 1초 소요된다. 그리고 현재 남은 음식은 3개 이므로 전체 k초에서 3초를 빼면 , 2번 음식을 제거한 후 남는 시간을 구할 수 있다.

 

2번 음식 제거후, 다음으로 가장 적은 시간이 걸리는 음식은 3번이다. 그러나 현재 음식 2개 남은 시점에서, 2*2초 는 남은 시간인 2초보다 크기 때문에, 이번에는 빼지 않는다.

남은 2초는 다음과 같을 것이다. 음식의 번호를 기준으로 정렬 한 후에, 남은 음식의 수 2로 나누면 나머지는 0이므로 1번 음식이 정답이 된다.

음식의 번호를 기준으로 정렬하면 -> [1번, 3번]

2(남은전체시간)%2(남은음식의 수) = 0

따라서 인덱스 0에 해당하는 1번이 정답이 된다.