[파이썬 PYTHON] 프로그래머스【무지의 먹방 라이브】

프로그래머스

 

확실히, 카카오 코테 기출문제라 그런지 어려웠다.

 

정확성 테스트는, 쉽게 풀 수 있었는데 효율성 테스트에서 점수 받는게 매우 힘들었고 결국 다른 사람들의 풀이를 참고했다..ㅎ

 

import heapq

def solution(food_times, k): 
    answer = -1
    
    # 음식 총합 보다 k가 크면 섭취할 음식이 없어지므로 -1 반환
    if sum(food_times) <=k:
        return -1
    
    foods = []
    # 우선순위 큐에 [음식양,음식번호] 입력, 음식양을 기준으로 오름차순 정렬이 되어있을 것
    for i in range(len(food_times)):
        heapq.heappush(foods,[food_times[i],i+1])
    
    eat = 0
    
    while foods:
        #음식을 다 먹는데 걸리는 시간 (최소부터)
        time = (foods[0][0]-eat)*len(foods)
        
        if time <= k:
            food, idx = heapq.heappop(foods)
            k-=time
            eat = food
        else:
            idx = k%len(foods)
            foods.sort(key=lambda x : x[1])
            return foods[idx][1]
    
    return answer

코드는 위와 같다.

 

사실상 while 문 들어가기 전가지는, 우선순위 큐에 [음식양, 음식번호]를 넣는 과정이고 while 문 부터가 이해가 좀 필요했다.

 

나름 내가 이해한 방법을 바탕으로 잘 설명을 해보겠다..ㅋㅋ

 

예제로 확인해보겠다.

---

현재 1번에 음식이 3개, 2번에 1개, 3번에 1개가 있는 상황이다.

 

그리고 우선순위 큐에 음식 양을 기준으로 입력하면 오른쪽과 같이 정렬된다.

 

그리고 모든 번호를 최소 음식양 만큼을 한 싸이클에 먹을 수 있는지 확인한다.

 

위 예시에선 최소 음식양이 1초이므로 총 3초가 걸린다.

 

k가 4초인 경우 1초가 남게 된다.

 

그러면 다음 최소 양인 3번으로 위 과정을 또 해본다.

 

다음 음식 최소양은 참고로 2가 아니라 1이다. 왜냐하면 첫 사이클에서 모든 번호의 음식이 1만큼 감소했기 때문이다.

 

그러므로 한 싸이클을 돌기 위해서는 2초가 필요한데 남은 k는 1이므로 한 싸이클을 돌 수 없어진다. 

 

 

 

싸이클을 돌 수 없는 상황이라면 다시 음식 번호 순으로 정렬 후, k를 이용해서 음식 번호를 찾으면 된다.

 

 

2번 음식은 다 먹었으므로 고려하지 않아도 되고, k가 1이므로 0~1초동안 1번을 먹고 방송이 중단되므로 

 

방송이 재개되었을때 먹을 음식은 3번이 된다.

 

즉, k가 최소 음식양으로 한사이클을 돌 수 없을 때, foods[k][1] 이 답이 된다.

---

 

위와 같은 경우는 k=2 에서 다음 음식 최솟값이 2초인데 한사이클을 도는데 4초가 걸리므로 싸이클을 돌 수 없어진다.

 

이 상황에서 다시 음식 번호순으로 정렬한 뒤, 중단 뒤 먹을 음식 번호를 구해야한다.

 

foods[k][1] 로 구하게 되면 인덱스 범위 오류가 생길 수 있다.

 

따라서 foods[k%len(foods)][1] 로 구해야한다. (foods는 다 먹은 음식은 포함되지 않음)

 

따라서 foods[0][1]이 되고 먹을 음식은 1번이 된다.