무지의 먹방 라이브

📌문제

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

프로그래머스

 

📌풀이

모든 음식을 시간 기준으로 정렬

시간이 적게 걸리는 음식부터 제거해나가는 방식

최소값을 빠르게 추출하기 위해 우선 순위 큐 사용

📌코드

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) #남은 음식 개수
    
    #sum_value+(현재 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    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]

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬