[Python] 프로그래머스 / level 4 / 무지의 먹방 라이브 / heapq / 그리디

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

프로그래머스

 

 

from collections import deque
def solution(food_times, k):
    sec = 0
    food_order = deque([idx, food] for idx, food in enumerate(food_times))
    
    while food_order:
        current = food_order.popleft()
        if current[1]==0:
            food_order.append(current)
            continue
        current[1] -=1
        food_order.append(current)
        sec += 1
        if sec==k+1:
            return current[0]+1

 

다음과 같이 큐로 풀 경우 시간초과로 테케 몇개는 실패한다.

그 이유는 나와 같이 풀게 되면 k번의 연산을 하게 되기 때문이다. -> 그리디로 풀어야 하는 이유

 

 

1) 이코테 풀이

 

import heapq
def solution(food_times, k):
    
    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]

 

역시나 아이디어는 똑같이 시간이 적게 걸리는 음식부터 제거해 나가는 방식 -> 우선순위 큐를 이용!

 

 

2) 

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

 

 

def solution(food_times, k):
    answer = 0
    length = len(food_times)
    foods = []
    
    for i in range(length):
        foods.append((food_times[i], i+1))
        
    foods.sort()
    
    pretime = 0
    
    for i, food in enumerate(foods):
        diff = foods[0] - pretime
        if diff != 0:
            spend = diff*n
            if spend<=k:
                k -= spend
                pretime = food[0]
            else:
                k%=n
                result = sorted(foods[i:], key=lambda x:x[1])
                return result[k][1]
        n -= 1
    return -1

 

 

모르겠다....다시 풀어봐야지