[프로그래머스] 무지의 먹방 라이브

https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3 

코딩테스트 연습 - 무지의 먹방 라이브

 

옛날에 java 로 풀었던 문제를 python 으로 풀어봤다.

 

1. heapq 를 이용하여 queue 에서 가장 작은 원소를 내보내면서 k 를 줄인다. 이 과정을 반복하여  queue 에서 남은 원소 중 가장 작은 것을 제거할 때 줄어든 k 보다 크다면 while 문을 종료시킨다.

 

2. 이때 남은 k 는 0 보다 같거나 큰 수로 현재 남은 queue 의 길이 (정확히는 len(queue) + 1) 만큼 나눈 나머지는 food_time[0] 을 기준으로 한 바퀴를 돌기 전까지의 남는 시간이다. 차례대로 for 문을 돌려 남는 시간이 없어졌을 때 해당하는 원소의 위치를 구해주면 된다. 

 

import heapq

def solution(food_times, k):
    answer = -1
    queue = []
    x, y = 0, 0
    
    for i in food_times:
        heapq.heappush(queue, i)
    
    while queue:
        x = heapq.heappop(queue)
        
        if k >= (x - y) * (len(queue) + 1):
            k = k - ((x - y) * (len(queue) + 1))
            y = x
        else:
            break
    
    r = k % (len(queue) + 1)
    
    for i in range(len(food_times)):
        if food_times[i] > y:
            r = r - 1
            if r < 0:
                answer = i + 1
                break

    return answer

print(solution([3, 1, 2], 5)) # 1