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

문제

---

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

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

 

풀이

---

이 문제는 효율성을 고려해서 풀 때 어떻게 해야할지 고민을 좀 하게된 문제입니다.

 

효율성을 고려하지 않은 경우 문제에 주어진 대로 시간이 1초씩 줄어듬에 따라 배열에 있는 숫자를 순차적으로 1씩 빼주는 과정을 거쳐주면 쉽게 풀립니다. 하지만 효율성 테스트의 제한 사항 입력 크기를 보면 이러한 방법은 당연하게도 시간초과가 날 것 같아 다른 방법을 생각해야만 했습니다.

 

가장 먼저 떠오른 생각은 다음과 같습니다.

k 값이 충분하다면 음식을 다 먹는데 드는 시간이 가장 적은 것부터 처리해버리자!

 

위와 같은 생각을 거치니 우선순위 큐라는 자료구조를 쉽게 떠올릴 수 있었고 heapq 모듈을 사용해 최소 힙을 구성했습니다.

최소 힙의 노드에는 [ 음식을 먹는데 드는 시간, 해당 음식의 index ] 두 가지 정보가 들어가게끔 구성했습니다. 해당 음식의 index는 답을 낼 때 필요한 정보이기 때문입니다.

 

주요 로직은 아래와 같습니다.

1. k 값이 충분하면 즉, 음식을 하나 다 먹을 수 있을 만큼 여러번 회전이 가능하면 그에 드는 시간만큼 k 값을 빼주고 heappop을 통해 음식 하나를 제거해줍니다. + 이 과정이 가능할 때 까지 음식을 제거해줍니다.

2. 위 과정을 반복하다보면 음식 하나를 다 먹을 수 없을 만큼 k 값이 작아지고 이때부터 heap을 index 기준으로 정렬하여 남은 k 값을 이용해 네트워크 중단 후 먹어야할 음식을 구해줍니다. => 먹어야할 음식의 index = k % len(heap)

 

 

풀이 코드는 아래와 같습니다.

from heapq import heappush, heappop

def solution(food_times, k):
    # 방송 중단 전 음식을 다 먹는 경우
    if sum(food_times) <= k:
        return - 1
    
    foodHeap = []
    length = len(food_times)    #남은 음식 개수
    for i in range(length):
        heappush(foodHeap, [food_times[i], i + 1]);
    
    time = 0
    while (foodHeap[0][0] - time) * length < k:
        k -= (foodHeap[0][0] - time) * length
        time += (foodHeap[0][0] - time)
        length -= 1
        heappop(foodHeap)
        
    result = sorted(foodHeap, key = lambda x : x[1])    # index를 기준으로 heap을 다시 정렬
    answer = result[k % length][1]
    return answer