[이코테] 무지의 먹방 라이브

이번 문제는 단순하게 주어진 k 시간만큼 모든 음식들을 접근하여 다음 인덱스를 찾게 되면 정확성 및 효율성으로 인해 틀리게 되는 문제이다.

 

따라서 소요 시간이 적게 걸리는 음식부터 하나씩 먹어 치운 후에, 주어진 k 시간에서 남은 시간동안 가장 적게 시간이 걸리는 음식을 먹지 못할 때 그 나머지 값을 인덱스로 리턴하면 풀리게 되는 문제이다.

 

이 문제의 핵심은 모든 음식을 소요 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 것이다.

 

이 문제를 접근하기 위해 내게 부족했던 파이썬 문법들은 다음과 같다.

1. '음식을 먹는게 소요되는 시간'과 '인덱스'를 동시에 저장하기 위해서 Tuple 자료형을 사용할 수 있다는 점
2. sorted나 .sort로 정렬할 때 두번째 인자로 key 값을 부여하여 인덱스 별로 정렬을 할 수 있다는 점
3. 우선순위 별로 값들을 정렬하고 제거하기 위해서 우선순위 큐(Priority Queue)를 사용할 수 있다는 점
4. 인덱스와 원소를 동시에 가져오기 위해서 enumerate() 함수를 사용할 수 있다는 점

풀이 1.

from operator import itemgetter

def solution(food_times, k):
    
    foods = []
    food_count = len(food_times) # 가로(남은 음식 개수)
    
    # 튜플 자료형으로 음식의 소요 시간과 인덱스를 저장
    for i in range(food_count):
        foods.append((food_times[i],i+1))
    
    # 튜플 자료형은 첫 번째 원소를 기준으로 정렬 !
    foods.sort()
    
    pretime = 0 
    
    # enumerate() 함수는 기본적으로 인덱스와 원소로 이루어진 튜플(tuple)을 만들어줍니다. 따라서 인덱스와 원소를 각각 다른 변수에 할당하고 싶다면 인자 풀기(unpacking)를 해줘야 합니다.
    for i,food in enumerate(foods):
        diff = food[0] - pretime # 세로(소요 시간)
        if diff != 0:
            spend = diff*food_count # 총 소요시간(세로 x 가로)

            if spend <= k: # 총 소요시간이 k보다 쟉은 경우
                k -= spend
                pretime = food[0]

            else: # 총 소요시간이 k 보다 오래 걸릴 경우
                k %= food_count # 나머지 계산
                sublist = sorted(foods[i:],key = itemgetter(1)) # 인덱스 기준으로 재정렬
                return sublist[k][1] # 정답 인덱스
            
        food_count -= 1 # 하나의 음식을 모두 섭취했으니 남은 음식 개수 최신화
        
    return -1

 

풀이2.

import heapq

def solution(food_times, k):
    
    if sum(food_times) <= k:
        return -1
    
    hq = []
    food_count = len(food_times)
    
    # 소요 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용(최소 Heap)
    for i in range(food_count):
        heapq.heappush(hq,(food_times[i],i+1))
        
    sum_value = 0 # 먹기 위해 사용한 시간
    pre_time = 0 # 이전에 다 먹은 음식 시간
    
    while sum_value + ((hq[0][0] - pre_time)*food_count) <=k:
        now = heapq.heappop(hq)[0]
        sum_value += (now-pre_time)*food_count
        food_count -= 1 # 다 먹은 음식은 남은 음식 개수에서 빼기
        pre_time = now # 이전 음식 시간 재설정
    
    result = sorted(hq,key=lambda x:x[1]) # 음식 번호(인덱스) 기준으로 정렬
    return result[(k-sum_value)%food_count][1]

 

두 풀이는 튜플 값 그 자체로 푸느냐, 우선순위 큐를 사용하느냐의 차이일 뿐 접근법은 동일하다.

 

파이썬의 문법이 다소 부족하여 제대로 풀지 못했지만 소요 시간이 적게 걸린 음식부터 정렬하여 처리하는 것과 음식의 번호(인덱스)를 기억한 뒤 재정렬 한다는 탐욕적(Greedy) 접근으로 풀이해야 한다는 사실을 기억해두도록 하자.