[Python] 프로그래머스 무지의 먹방 라이브 | Heap(힙) | 2019 KAKAO BLIND RECRUITMENT

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- 가장 작은 시간이 걸리는 음식 부터 처리한다. (heapq 사용)

- 만약 모든 음식의 개수 보다 k가 크다면 모든 음식을 먹고도 시간이 남는 것이므로 -1 반환

- 한번의 로테이션을 위해 필요한 음식 개수는, 0이 아닌 음식의 수이다.(length)

- (다음 최소 음식 개수) - (이전에 처리한 음식 개수) = 현재 처리해야할 음식의 최소 개수

 

- 만약 'k - (최소 음식 개수)*(로테이션) < 0' 이라면 반복문을 종료한다.

- 남은 음식들의 순서를 음식 크기가 아닌 번호대로 다시 정렬 후 

   남은 k번의 횟수에 대해서 몇번의 로테이션을 돌 수 있는지(k % length) 구하여 최종 위치를 찾는다.

 

 

작성 코드

 

import heapq


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


    length = len(food_times)  # 한 번의 로테이션을 위해 남은 음식 개수
    previous = 0  # 이전 처리 음식

    que = []
    for i, time in enumerate(food_times):  # (시간, 번호) 힙 삽입
        heapq.heappush(que, (time, i + 1))

    while k - (que[0][0] - previous) * length >= 0:
        time, now = heapq.heappop(que)  # 처리할 가장 작은 음식
        k -= (time - previous) * length
        previous = time
        length -= 1  # 한 번의 로테이션 처리

    que.sort(key=lambda x: x[1])  # 음식 번호로 재정렬
    return que[k % length][1]  # 남은 음식 수에 대한 로테이션 후 최종 위치

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://mjmjmj98.tistory.com/149

https://www.youtube.com/watch?v=zpz8SMzwiHM