[프로그래머스] - 무지의 먹방 라이브 (파이썬)

# 무지의 먹방 라이브
import heapq


def solution(food_times, K):
    answer = -1
    food = []
    for i in range(len(food_times)):
        heapq.heappush(food, (food_times[i], i+1))

    prev = 0
    l = len(food)
    while food:
        temp = (food[0][0] - prev) * l
        if K >= temp:
            K -= temp
            prev, _ = heapq.heappop(food)
            l -= 1
        else:
            index = K % l
            food.sort(key=lambda x: x[1])
            answer = food[index][1]
            break

    return answer

 

2019 카카오 블라인드 - 4번

1. food를 food_times가 짧은 순으로 최소힙으로 구성한다. 해당 음식의 인덱스도 추가

2. food를 다 먹을 때 까지

    - prev = 직전음식을 먹는데 걸린 시간, l = 남은 음식의 수

    - 해당 음식의 시간 * 한바퀴 =< K 이면, K에서 빼주고, 음식을 다 먹었으므로 prev에 pop해서 넣어주고 l -= 1

    - 남은 시간 K보다 커진다면 K를 l로 나눈 나머지를 index에 넣어주고 food를 index롤 정렬해준다.

    - 이후 해당 인덱스의 값을 answer로 반환

3. anwer 출력

 

 

아이디어를 떠올리는데 오래걸렸다.

효율성 테스트를 보니 시간복잡도를 최대한 줄이기위해 가장 적게 남은 음식을 기준으로

n바퀴씩 먹어서 K에서 빼주는 형식을 접근해야한다.