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

문제

무지의 먹방 라이브

문제 해설

일단, 효율성 테스트에서 k의 값이 20조이하가 주어집니다. 여기서 생각할 수 있는 것은 절대 완전탐색으로는 효율성 테스트를 통과할 수 없다 입니다. 저도 완전탐색으로 처음에 쉽게 접근했다가 효율성 테스트에서 무릎을 꿇었습니다.

우선 순위 큐를 이용하여 문제를 접근하면 시간을 단축시킬 수 있습니다. 하지만 계산하는 과정이 꽤나 복잡하므로 직접 해보시며 식을 찾는 것을 권장합니다.

1. 우선순위 큐에 (food_times, 음식 번호)를 담습니다.
2. 현재 큐의 길이를 변수에 저장합니다.
3. (pop한 요소 - 전에 pop했던 요소)와 현재 큐의 길이를 곱합니다. 이렇게 하는 이유는 큐의 길이가 계속 바뀌고, 전에 pop 했던 요소를 알아야 k번째의 음식번호를 구할 수 있기 때문입니다. 만일 이 계산 값이 k를 넘지 못하면 2번으로 돌아갑니다.
4. 값이 k를 넘어서면 지금 큐에 있는 음식으로 k를 구할 수 있다는 의미입니다.

풀이 코드

import heapq
def solution(food_times, k):
    answer = 0
    time = 0
    pq = []
    answer_rs = []
    # 1. 우선순위 큐에 (food_times, 음식 번호) 순으로 담는다.
    for i in range(len(food_times)):
        heapq.heappush(pq, [food_times[i], i + 1])

    pre_food = 0
    flag = True
    while flag:
        if not pq:
            return -1
        length = len(pq)
        time += (pq[0][0] - pre_food) * length
        if time > k:
            time -= (pq[0][0] - pre_food) * length
            while pq:
                answer_rs.append(heapq.heappop(pq)[1])
            answer_rs.sort()
            answer = answer_rs[(k - time) % length]
            flag = False
        else:
            pre_food = heapq.heappop(pq)[0]
    return answer