무지의 먹방 라이브

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

프로그래머스

문제를 요약하자면 k초까지 음식을 먹고 난 다음 차례를 구하는 문제라 할 수 있을 것 같습니다.

 

1차 시도

food_times를 매번 다 돌기보다는 음식이 남아있는 인덱스만 돌자라는 생각으로 구현했습니다.

def solution(food_times, k):
    N = len(food_times)
    
    leftovers = [idx for idx in range(N)]
    
    cur = 0
    
    while 0 <= k:    
        if leftovers == []:
            return -1
        
        repeat_leftovers = leftovers.copy()
        
        for left in repeat_leftovers:
            if k == 0:
                return left+1
            
            food_times[left] -= 1
            k -= 1
            
            if food_times[left] == 0:
                leftovers.remove(left)

 

결과

 

정확성은 통과하였지만 효율성에서 다 실패했습니다.

 

2차 시도

queue를 이용해보자는 생각으로 구현했습니다.

import queue

def solution(food_times, k):
    food_queue = queue.Queue()
    for idx, food_time in enumerate(food_times):
        food_queue.put((food_time, idx+1))
    
    while not food_queue.empty():
        food_time, idx = food_queue.get()
        if k == 0:
            return idx
        food_time -= 1
        k -= 1
        if food_time:
            food_queue.put((food_time, idx))
    return -1

 

결과

가독성은 늘어났으나 실행시간은 더 느려졌습니다. (1차 시도와 마찬가지로 정확성만 통과)

 

3차 시도

다른 사람의 코드를 참고하였고, 음식을 섭취하는데 걸리는 시간을 오름차순으로 정렬한 후,

현재 음식의 섭취하는데 걸리는 시간과 다음 음식의 섭취하는데 걸리는 시간을 비교하여 for문을 도는 횟수를 줄이자는 생각으로 구현했습니다.

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    
    food_queue = []
    for idx, food_time in enumerate(food_times):
        heapq.heappush(food_queue, (food_time, idx+1))
    
    times = 0
    previous_time = 0
    left_food_count = len(food_queue)
    
    while times + (food_queue[0][0] - previous_time) * left_food_count <= k:
        food_time = heapq.heappop(food_queue)[0]
        times += (food_time - previous_time) * left_food_count
        left_food_count -= 1
        previous_time = food_time
        
    leftovers = sorted(food_queue, key=lambda x: x[1])
    return leftovers[(k-times)%left_food_count][1]

 

결과

정확성과 효율성 모두 통과했습니다.

 

설명

heapq를 이용하여 food_queue를 섭하는데 걸리는 시간을 기준으로 우선순위 큐를 만듭니다.

 

현재까지 섭취한 시간인 times, 이전까지 섭취한 시간인 previous_time, 남은 음식 개수인 left_food_count를 초기화합니다.

while문으로 현재 음식과 다음 음식의 섭취 시간 차이 * 남은 음식 수가 현재 섭취 시간에 더해질 때 시간과 k초를 비교합니다.

※ 여기서 food_queue[0][0]이 다음 음식 섭취시간이고, previous_time가 현재 음식 섭취시간입니다.

 

k초를 넘지 않는다면, 다음 음식을 다 섭취하는 루틴으로 넘어가게 됩니다.

이 루틴에서 food_queue에서 다음 음식을 빼내고, times가 다음 음식을 다 섭취할 때의 루틴의 섭취 시간으로 초기화 되고, left_food_count에 1을 빼고, previous_time을 다음 음식 섭취 시간으로 초기화합니다.

 

k초를 넘는다면, k초에 times를 빼고 left_food_count로 나눈 나머지의 위치에 있는 음식 번호를 return 해주게 됩니다.

 

만약 전체 음식을 다 섭취하는데 걸리는 시간이 k초보다 작다면 이후 로직을 탈 필요가 없기 때문에,

맨위에서 if  sum(food_times) <= k의 조건문을 추가했습니다.