[이코테] 그리디 - 무지의 먹방 라이브

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

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

사고과정

• 그리디 방식을 전혀 생각하지 못하고 그냥 순차적으로 음식을 먹는 방향으로만 생각했다. 애써 구현했으나 틀림..
• 풀이를 보았는데 하루종일 붙잡고 이해하려고 애썼다.. 핵심은 음식을 먹는 데 가장 적게 드는 비용의 음식부터 먹어치우는데, 이 때 회전판으로 음식이 돌아가기 때문에 한 음식을 다 먹는다고 하면 다 먹는 과정을 거치는 동안 다른 음식들도 1초씩 무조건 먹어야 함. 그래서 이제 먹으려는 음식의 시간을 계산할 때, 직전에 먹었던 음식을 먹는 데 소요되는 시간을 빼주어야 함. 이부분을 이해하는 데 매우 오래 걸렸다.. 이것에 관해 깃헙에도 이슈가 있었다..
• 가장 적은 비용의 음식부터 먹어야 하기 때문에 우선순위 큐를 활용함.
• 마지막에 k초 후에 먹어야 할 음식 번호를 출력해야 하는데, 소스코드 마지막 줄에 (k-sum_value) % length 코드가 직관적으로 이해되진 않는다.. 그냥 경험적으로 몇 개 예시를 생각해보고 일정의 규칙을 발견해서 작성한 건가..? 아니면 일종의 법칙 처럼 작성한 것인가 모르겠다.. 이러한 룰을 만들어내는 것도 대단한듯싶다.. 결국 k초 중에 남은 초를 남은 음식 개수로 나눈 나머지를 의미하는데, 이게 어떻게 k초 이후에 섭취해야 할 음식 번호가 있는 인덱스를 딱 가리키는 건지 신기하다..
• 한 10번,20번까지 풀어봐야 할 듯하다.

풀이(스스로 못 푼 풀이)

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)  # 남은 음식 개수

    # 지금까지 이전 음식 먹는 데 사용한 총 시간 + (이제 먹을 음식 시간 - 직전에 먹은 음식 시간) * 남은 음식 개수 -> 직전에 먹은 음식 시간을 빼주는 이유는 회전판이 돌 동안 이제 먹을 음식을 일부 먹었을 것이므로!
    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]