프로그래머스 무지의 먹방 라이브 (Python)

문제 링크

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

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

---

Test Case

---

문제 풀이

처음에 그냥 무지성으로 반복문 돌려가면서 음식 하나씩 먹다가 정답을 구하는식으로 풀었다가 효율성에서 걸렸다. 이코테 책에서 난이도 1이라고 하길래 쉽게 풀리나 했는데 역시나 틀렸다.

문제풀이는 우선순위큐를 사용해서 정렬 한 뒤 각 음식마다 남은 양을 하나씩 먹어치우는게 아니라 한 cycle씩 먹어서 최대한 빨리 답을 도출하는 것이다. 여기서 말하는 cycle 은 while문의 조건인데, 남은 음식들을 하나씩 다 먹는 것, 그러니까 첫번째 음식 부터 마지막 음식까지 먹게되는 시간을 의미하고 그 cycle이 문제에 주어진 네트워크가 끊기는 시간보다 적을 동안 반복한다.
그 다음 남은 시간은 한 cycle보다 작은 시간들이므로 k에서 음식 먹은 시간 합을 빼서 남은 음식들 개수로 나눠 준 값이 답이 된다.

그림으로 표현하면 쉬운데 말로 표현하려다보니 조금 어려운 문제인듯 하다.

---

Source Code

import heapq
import sys
input = sys.stdin.readline

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

    length = len(food_times)
    q = []  # 음식시간, 음식번호 순
    for i in range(length):
        heapq.heappush(q, (food_times[i],i+1))

    sum_time, prev_time = 0, 0
    # sum_time : 여태까지 먹은 음식 시간 합
    # prev_time : 이전에 먹은 음식 시간
    while sum_time + ((q[0][0] - prev_time) * length) <= k:
        now_time = heapq.heappop(q)[0]
        sum_time += (now_time - prev_time) * length
        prev_time = now_time
        length -= 1
    
    # 우선순위큐 -> 음식번호순 
    result = sorted(q, key = lambda x:x[1])
    return result[(k - sum_time) % length][1]

food_times = list(map(int, input().split()))
k = int(input())

print(solution(food_times,k))