[python] 프로그래머스 42891번 : 무지의 먹방 라이브 (heapq 사용)

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

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

 

 

1-1. 효율성 통과하지 못한 코드 

from collections import deque
def solution(food_times, k):
    answer = 0
    if sum(food_times) <= k:
        return -1
    deq = deque()
    for idx, time in enumerate(food_times):
        deq.append((idx+1, time))
    # print(deq)
    for i in range(k+1):
        while True:
            number, time = deq.popleft()
            if time != 0:
                break
        deq.append((number, time-1))
        if i == k:
            answer = number
    return answer

 

 

1-2. 효율성 통과하지 못한 코드 

from collections import deque

def solution(food_times, k):
    deq = deque()
    for i in range(1, len(food_times)+1):
        deq.append((i, food_times[i-1]))

    for t in range(1,k+2):
        # print(t, '초')
        if deq:
            number, time = deq.popleft()
            # print(number, time)
            if t == k+1:
                return number
            if time-1 == 0:
                # print('after..', deq)
                continue
            deq.append((number, time-1))
            # print('after..', deq)
        else:
            return -1

 

 

2. 정답인 코드 

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
    print(q)
    result = sorted(q, key=lambda x: x[1])
    # (k - sum_value) => 3 
    # length = 2
    # 3초 후에 선택될 데이터를 return 
    # 0  1
    # 2 '3'
    # [(8,1),(6,2)]
    return result[(k - sum_value) % length][1]