무지의 먹방 라이브(2019 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

처음 이 문제를 풀었을 때, 총 k번 while문을 돌면서 해당 음식마다 1초를 감소 시켜 주었다. k는 2,000,000 이하의 자연수가 들어가기 때문에, 위 방법으로 풀었을 때 효율성 테스트에서 전부 통과하지 못했다.

 

해당 문제는 그리디 알고리즘으로 문제를 해결 할 수 있다.

 

먹는데 시간이 적게 걸리는 음식부터 우선적으로 제거해나가는 방식을 사용면된다. 시간이 적게 걸리는 음식을 정렬 할 땐 우선순위 큐를 사용하면된다. 

 

음식을 1초간 돌아가면서 먹기 때문에, 특정 음식을 다 먹는 시간은 (음식의 갯수 * 특정 음식을 다 먹는데 걸리는 시간)을 통해서 구할 수 있다.

 

만약 3, 1, 2의 음식들이 주어져있다면, 세번째 음식을 다 먹기 위해서는 총 두바퀴를 돌아야 다먹을 수 있다. 때문에 2 * 3(음식 갯수) 즉, 6초가 지나야 세번째 음식을 다 먹을 수 있다. 물론 두 바퀴를 돌기전에 2번 음식을 다 먹어버리므로 실제 걸리는 시간은 5초이다.

 

그리고 두 바퀴를 돈다는것은 해당 음식만 먹는것이 아니기에 다른 음식들도 2 씩 감소시켜 주어야한다. 때문에 5초가 지나면 남은 시간은 각 1, 0, 0 이된다.

 

이제 실제 예시를 들어보면서 문제를 이해해보자.

 

k가 15로 주어지고 다음과 같은 음식들이 주어져있다고 해보자. 참고로 마지막에 몇번째 음식을 먹어야 하는지 알아야 하기 때문에, 먹는데 걸리는 시간과 음식의 인덱스를 튜플로 같이 저장 해주어야 한다.

 

[8, 6, 4]

 

해당 음식들을 우선순위 큐에 집어넣으면 제일 적게 걸리는 3번째 음식이 가장 앞으로 정렬된다. 세번째 음식을 제거하기 위해서는 4초 * 3(음식수) 총 12초가 걸린다.

 

결과적으로 남은 시간은 15 - 12 즉, 3초가 남는다.

 

3번째 음식을 다 먹었기 때문에 음식 수는 2로 줄어든다. 그리고 남은 음식들은 네 바퀴를 돌았기에 각각 4초씩 줄어든다.

 

[4, 2]

 

이 때 다음으로 적게 걸리는 시간은 2초이며, 음식은 2개가 있으므로 해당 음식을 다먹기 위해서는 2 * 2 ,즉 4초가 필요하다. 하지만 지금 남아있는 시간은 3초이므로 해당 음식을 다 먹진 못한다.

 

따라서 다음으로 먹어야 할 음식의 번호를 찾아서 출력하면 된다. 3초가 남았으므로 첫번째 음식을 반환해주면 된다.

 

이를 코드로 옮기면 다음과 같다.

 

from heapq import heappush, heappop
def solution(food_times, k):

    # 주어진 초가 전체 음식을 먹는데 충분하다면 -1을 반환 
    if sum(food_times) <= k:
        return -1
    
    # 먹는데 걸리는 시간이 적은 음식을 먼저 다 먹어주어야 하므로 우선순위 큐를 사용해준다.
    q = []
    for i in range(len(food_times)):
        heappush(q, (food_times[i], i + 1))

    # 음식을 먹기 위해 사용한 시간
    sum_value = 0

    # 직전에 다 먹은 음식의 시간을 저장
    
    previous = 0 

    # 먹고 남은 음식의 수
    length = len(food_times)

    # 이전에 음식을 다 먹음으로써 감소한 시간을 다른 음식들에도 적용해 주어야한다. -> previous를 빼주면된다.
    while sum_value + (q[0][0] - previous) * length <= k:
        now = heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1
        previous = now

    # 인덱스 순으로 다시 정렬해준다.
    result = sorted(q, key=lambda x : x[1])
    # '남은' 음식 중에서 몇 번째 음식인지 확인하며 출력
    return result[(k-sum_value) % length][1]