2019 카카오 블라인드 코딩테스트 - 무지의 먹방 라이브

이 문제는 정확성과 효율성을 모두 보는 문제이다.
테스트 케이스의 범위만 보더라도 효율성에서는 k의 값이 200조이기 때문에
k의 값을 1부터 증가시키는 선형적 방법으로는 절대 풀수 없음을 알 수 있다.

정확성만 통과하는 솔루션

deque 을 이용해 계속 왼쪽으로 빼거나 rotate 해서 풀 수 있다.

from collections import deque

# 이 솔루션은 정확성만 통과한다.
def solution(food_times, k):
    deq = deque()
    total = 0
    for i, time in enumerate(food_times):
        deq.append([i+1, time])
        total += time
    
    if total <= k:
        return -1

    num = 0
    while True:
        if num == k:
            return (deq[0][0])
        if deq[0][1] > 0:
            deq[0][1] -= 1
            if deq[0][1] == 0:
                deq.popleft()
            else:
                deq.rotate(-1)
            num += 1

    answer = 0
    return answer

정확성, 효율성 모두 만족하는 솔루션

heapq 를 이용해 가장 작은 time 부터 모든 배열 전체에서 빼준다.
이 때 실제 배열에서 빼게 되면 매번 최대 1억번의 반복을 하기 때문에 시간초과가 난다.
따라서 모든 배열에서 뺀 값을 더해서 항상 k 와 비교하는 방법을 택한다.
prev 값을 이용하는 이유는 이전에 뽑은 가장 작은 time 과 현재 가장 작은 time 의 차이만큼 빼야 하기 때문이다.
마지막으로는 다시 인덱스를 이용한 정렬을 함으로써 구하려고 하는 위치를 알아낸다.

import heapq

# 이 솔루션은 정확성과 효율성 모두 통과한다.
def solution(food_times, k):
    
    if sum(food_times) <= k:
        return -1
    
    heap = []
    for i, time in enumerate(food_times):
        heapq.heappush(heap, (time, i+1))
        
        
    sum_value = 0
    prev = 0
    length = len(food_times)
    
    while sum_value + ((heap[0][0] - prev) * length) <= k:
        cur = heapq.heappop(heap)[0]
        sum_value += ((cur - prev) * length)
        length -= 1
        prev = cur
        

    result = sorted(heap, key = lambda x: x[1])
    return result[(k - sum_value) % len(heap)][1]