[Programmers] 무지의 먹방 라이브

[Programmers] Q42891 무지의 먹방 라이브

Question

Language: Python

1번 음식부터 시작해서 순차적으로 옆에 있는 음식들을 먹어 가는 과정을 쭉 반복해서 k 번째 됬을 때 먹고 있는 음식의 종류를 알아야한다.

아 그럼 그냥 반복문으로 쭉 돌려보면 되지 않을까?, 하지만 이 문제는 효율성 테스트에 대한 제한 사항이 존재한다. 따라서, 처음 부터 끝까지 돌려보면 문제를 올바르게 해결할 수 없다.

이 문제는 음식을 하나씩 소거해가면서 문제를 해결한다. 음식의 종류가 [3,1,2] 와 같이 있을때, 이때의 최소 값은 1이다. 따라서 2번 음식을 다 먹기까지는 1*length(3) 시간이 요구된다. 이렇게 되면 3초가 흐른 것이다. 다음 남은 음식[2,0,1]중에서 가장 작은 값은 3번 음식이다. 3번 음식을 다 먹기까지 요구되는 시간은 2초이다. 그러면 3번 음식까지 다 먹게 되면 총 흐른 시간은 5초이다. 그리고 남은 음식은 [1,0,0]으로 1번만 남는다. 5초후에 먹어야하는 음식은 1번이다.

만약 4초후에 먹어야하는 음식을 구해야된다면 어떻게 해야될 까?

3초동안(2번 음식을 단 먹는데 걸리는 시간) 먹고 나면 [2,0,1]이 되고, 남은 음식 중 가장 작은 음식인 3번을 모두 먹기에는 시간이 부족하다. 따라서, 남은 음식 리스트[2,1]에서 (K-지금까지 먹은 시간) 남은 시간이 1초이고, length가 2이므로, 남은 음식 중 두번째 인덱스인 3번 index라고 할 수 있다.

또한, 음식 하나씩 소거해가면서, 남은 것 중에서 최소값을 구하기 위해 heap 자료구조를 사용하면 효율을 높일 수 있다.

Fail Code

import heapq
def solution(food_times, k):
    if sum(food_times) <=k:
        return -1
    heap=[]
    length=len(food_times)
    for i in range(length):
        heapq.heappush(heap,(food_times[i],i+1))
    
    sub_sum=0
    while sub_sum + ((heap[0][0])*length) <=k:
        item=heapq.heappop(heap)[0]
        sub_sum+=item*length
        length-=1
    
    heap.sort(key=lambda x: x[1])
    answer=heap[(k-sub_sum)%length][1]
    return answer

처음에는 위와 같이 구현했는데, 틀렸다고 나왔다. 하지만, 다시 잘생각해보니, 이전 음식을 먹고나면, 그 만큼 음식의 양이 줄어야하는데, 이 부분을 고려하지 못했다. [3,1,2]에서 1번 순환을 하게 되면 [3-1,1-1,2-1]이 되고 다음 최소값이 1이된다.

import heapq
def solution(food_times, k):
    if sum(food_times) <=k:
        return -1
    heap=[]
    length=len(food_times)
    for i in range(length):
        heapq.heappush(heap,(food_times[i],i+1))
    
    sub_sum=0
    prev=0
    while sub_sum + ((heap[0][0]-prev)*length) <=k:
        item=heapq.heappop(heap)[0]
        sub_sum+=(item-prev)*length
        prev=item
        length-=1
    
    heap.sort(key=lambda x: x[1])
    answer=heap[(k-sub_sum)%length][1]
    return answer