[그리디 알고리즘] 무지의 먹방 라이브 - 파이썬(python)

무지의 먹방 라이브

난이도 : 下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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))
    
    used = 0
    previous = 0
    remain = len(food_times)
    
    while (used + ((q[0][0] - previous) * remain) <= k):
        now = heapq.heappop(q)[0]
        used = used + (now - previous) * remain
        remain = remain - 1
        previous = now

    answer = sorted(q, key=lambda x: x[1])
    return answer[(k - used) % remain][1]

---

예시

 

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    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 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

---

해설

 

우선순위 큐 알고리즘을 사용하여 푸는 문제였습니다. 처음에 리스트를 사용하여 풀었는데 효율성 문제 때문에 우선순위 큐를 사용하는 것이 좋아보입니다. 리스트의 시간 복잡도는 O(N), 우선순위 큐의 시간 복잡도는 O(logN)