[ 프로그래머스 / 파이썬 ] 무지의 먹방 라이브

🔗 Link

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

프로그래머스

 

🧩 Source Code

import heapq

def solution(food_times, k):
	# 모든 음식을 다 먹을 수 없는 경우
    if sum(food_times) <= k:
        return -1  
    
    heap = []
    for i, time in enumerate(food_times):
        heapq.heappush(heap, (time, i + 1))
    
    total_time = 0
    prev_time = 0
    food_count = len(food_times)
    
    while heap:
        time, index = heap[0]
        cycle_time = (time - prev_time) * food_count
        
        if total_time + cycle_time > k:
            break
        
        total_time += cycle_time
        prev_time = heapq.heappop(heap)[0]
        food_count -= 1
    
    remaining_foods = sorted(heap, key=lambda x: x[1])
    return remaining_foods[(k - total_time) % food_count][1]

---

 

📝 Commentary

무지의 먹방 라이브라 그런지 무지 어려웠다

 

문제를 보자마자 일반적으로 풀면 시간초과가 날 것이라고 생각을 했다.

정확성 테스트 제한 사항
food_times 의 길이는 1 이상 2,000 이하이다.
food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항
food_times 의 길이는 1 이상 200,000 이하이다.
food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
k는 1 이상 2 x 10^13 이하의 자연수이다.

 

logn의 시간 복잡도로 해결을 해야할 것 같았는데

 

그렇다면 2가지의 알고리즘을 떠올려야한다.

1. 이분 탐색

2. heapq

 

2개의 알고리즘으로 어떻게 풀 것인지에 대해 고민을 했고

time을 구하는 것이 문제였다면 이분 탐색으로 했겠으나 이 문제는 리스트를 순회하면서 계속 갱신이 되기 때문에

heapq를 써야겠다고 판단이 들었다.

import heapq

def solution(food_times, k):
	answer = 0
	return answer

 

이렇게 썼는데 꽤나 막막했다. 레벨 4를 풀 수 있을 것인가? 하지만 다시 집중해서 풀어봤다.

 

1. 예외 처리 ( 더 섭취해야 할 음식이 없는 경우 )

	 # 모든 음식을 다 먹을 수 없는 경우
	if sum(food_times) <= k:
        return -1

 

 

이러한 예외는 early return을 해주는 것이 코드의 진행에 있어서 좋다.

 

2. 변하는 리스트에서 인덱스 처리

food_times에서는 음식의 시간이 줄어들 때마다 0이 되고 이를 건너뛰고 세어줘야 한다.

heapq를 사용하면 최소 시간부터 떼서 사용할 수 있고 여기에 인덱스를 같이 넣어줬다.

    heap = []
    for i, time in enumerate(food_times):
        heapq.heappush(heap, (time, i + 1))

 

 

3. 가장 적은 시간 기준으로 싸이클 돌리기

    total_time = 0
    prev_time = 0
    food_count = len(food_times)
    
    while heap:
        time, index = heap[0]
        cycle_time = (time - prev_time) * food_count
        
        if total_time + cycle_time > k:
            break
        
        total_time += cycle_time
        prev_time = heapq.heappop(heap)[0]
        food_count -= 1

 

[ 12, 5, 7 ] 이런 식으로 있다고 생각을 해보면 굳이 3번씩 for문을 5번 돌릴 필요는 없다.

 

가장 작은 애(heap[0])를 찾아서 곱하기 전체 길이(food_count)를 해주면 되니깐.

 

그러한 로직을 바탕으로 작성했다.

 

싸이클이 한번 돌아서 5(prev_time)를 찾아낸 경우에 7(time)을 뽑을때는

 

7 - 5를 해주고 거기에 전체 길이(food_count)를 곱해주면 된다.

 

그렇게 남아있는 시간을 갱신해주면서 음식을 다 먹거나 (while heap) 혹은 시간이 됐을때(if total_time + cycle_time > k)까지 진행한다

 

4. 결과 반환

    remaining_foods = sorted(heap, key=lambda x: x[1])
    return remaining_foods[(k - total_time) % food_count][1]

 

x[1]에는 인덱스가 들어가있고 이를 기준으로 정렬해주면 처음 리스트와 똑같은 형태로 된다.

 

그 후 싸이클이 돈 만큼 빼주고 해당 인덱스의 나머지를 return해준다.

---