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

이번에 해결해 볼 문제는 프로그래머스에 있는 무지의 먹방 라이브이다.

---

문제 설명

1. 회전판에 먹어야 할 N개의 음식이 있다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다
2. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
3. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
4. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
5. 무지가 먹방을 시작한 지 K초 후에 몇 번 음식부터 섭취해야 하는지 출력

문제 예시

• 1번 ~ 3번 음식이 있을 때 해당 음식을 다 먹는데 걸리는 시간을 food_times에 음식의 번호 순서대로 저장
• food_times = [3, 1, 2]이고 K = 5초 후 몇 번 음식부터 섭취해야 하는지 알아보자.

문제 해결 아이디어

• 해당 문제를 이해하면 그리디 알고리즘을 떠올릴 수 있다. 왜냐하면 음식을 다 먹는데 걸리는 시간이 가장 짧은 것부터 회전판에서 없어지는 것을 알 수 있기 때문이다. 따라서 해당 문제에서는 음식을 다 먹는데 걸리는 시간이 가장 짧은 것부터라는 욕심을 낼 수 있다.
• 해당 문제의 출력은 음식의 번호이지만 문제를 해결하는 것은 음식을 다 먹는데 걸리는 시간이다. 따라서 우선순위 큐를 사용하여 시간을 기준으로 정렬할 수 있다.
• 위의 문제 예시에서 K = 6인경우를 생각해보면 문제의 요구에 따라 -1을 출력해야한다. 이를 일반화해보면 sum(food_times) <= K인 경우와 같다.

문제 해결 코드

def solution(food_times, k):
    import heapq

    if sum(food_times) <= k:
        return -1

    food_len = len(food_times)
    queue = []
    for i in range(food_len):
        heapq.heappush(queue, (food_times[i], i+1))

    sum_val = 0
    previous = 0
    while sum_val + (queue[0][0] - previous) * food_len <= k:
        now = heapq.heappop(queue)[0]
        sum_val += (now - previous) * food_len
        previous = now
        food_len -= 1
    result = sorted(queue, key = lambda x : x[1])
    answer = result[(k-sum_val) % food_len][1]

    return answer

간단한 예시

• 위의 그림은 작성한 코드의 while문을 나타낸 것이다.
• while문이 종료된 이후에 남아있는 음식들 중 (k-sum_val) % food_len번 째 음식을 고르면 정답이 된다.