[카카오] 무지의 먹방 라이브

출처:: 2019 카카오 신입 공채 https://programmers.co.kr/learn/courses/30/lessons/42891

분류:: 그리디

 

1. 문제 이해 및 해결과정

- 모든 음식을 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용한다는 아이디어까지는 생각하였다.

 

2. 풀이방법

 1. 그리디(최소힙)

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 + (현재의 음식시간 - 이전 음식 시간)*현재 음식 개수 vs 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] #남은 시간 % 남은 음식 
    
   

 

 

 

3. 오답원인

  1. 풀이 오류

def solution(food_times, k):
    answer = 0
    foodlen=len(food_times)
    li=[]
    for i in range(foodlen):
        li.append((food_times[i],i+1))
    li.sort()
    
    answer=-1
    for i in range(foodlen):
    
        k-=li[i][0]
        if k<0:
            answer=li[i][1]
            break

        
    #print(li)
    return answer

4. 알게된 점