[프로그래머스] Level 4 - 무지의 먹방 라이브 (Python)

 

 

 

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

프로그래머스

 

 

 

 

 

✅ Solution

• 우선순위 큐, heap를 이용하여 문제를 풀었다. 
• 먼저 heapq에 (음식 시간, 음식 번호) 순으로 넣어준다. 그럼 작은 순서대로 정렬이 된다. 
• 이제 queue를 앞에서부터 돌면서 해당 음식을 다 먹기까지 걸리는 시간을 계산해 준다.
  • 이때, 현재까지 걸린 시간 (sum_time)과 해당 음식을 다 먹는 데 걸리는 시간을 더했을 때 k 보다 크다면 탈출하도록 while 문을 작성했다. 
  • 예를 들어, 문제의 예시대로 queue에 넣으면 [(1, 2), (2, 3), (3, 1)] 순서대로 들어가게 된다. 
  • 처음에 sum_time, prev_time을 0, 0으로 설정해 준 뒤 가장 앞 요소부터 계산해 준다.
  • 1 (소요 시간) * 3 (남아있는 음식의 길이) = 3으로 첫 번째 요소는 3초가 지난 후 다 먹게 되는데 이 시간을 k에서 빼준다. (k = 5-3 = 2)
  • 다음으로 남은 음식인 (2,3)을 계산해줘야 하는데, 앞 요소에서 3초가 지났으니 2 (소요 시간) - 1 (이전 요소의 소요시간, prev_time) = 1 * 2 (남아있는 음식의 길이) = 2이다.
  • 다음 요소에서는 sum_time 조건에 걸려 while 문을 탈출하게 되고 [(3, 1)] 만 남게 된다.
• 남은 요소를 다시 음식 번호순으로 정렬해 준다.
• 남은 시간 (k - sum_time) 때 먹게 되는 음식을 출력한다.

 

 

 

 

 

✅ Code

import heapq

def solution(food_times, k):
    
    if sum(food_times) <= k:
        return -1
    
    queue = []
    sum_time, prev_time, length = 0, 0, len(food_times)
    
    for idx, time in enumerate(food_times):
        heapq.heappush(queue, (time, idx + 1))
        
    while sum_time + ((queue[0][0] - prev_time) * length) <= k:
        now = heapq.heappop(queue)[0]
        sum_time += ((now - prev_time) * length)
        length -= 1
        prev_time = now
        
    queue = sorted(queue, key=lambda x:x[1])
    
    return queue[(k - sum_time) % length][1]