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

무지의 먹방 라이브

생각흐름

1. 이전에 내가 못 풀었던 문제이다.
2. k값을 어떤 방식으로 빼느냐가 관건이다.
3. 배열 인덱스를 잘 다뤄야 하는 문제이다.
4. 음식들을 다 먹게 되는 사이클의 크기만큼 줄여나가보도록 하자
   1. 사이클이 너무 크다.
   2. 사이클이 너무 큰데다가, 남은 음식을 몇 바퀴 돌아야 k값이 0이 되는 경우를 해결 못함
   3. 2번의 경우를 캐치하지 못한다면 어떤 곳에선 -1이 나와버리는 불상사 -> 정확성 실패
5. 음식들 길이만큼의 사이클로 줄여보자
   1. 정확성은 맞는다.
   2. 효율성에서 실패한다.
6. 4번과 5번을 결합하자.
7. 4번대로 하다가 k값이 부족해지면 5번을 돌린다.
   1. 효율성에서 하나가 실패한다...
8. 5번을 돌릴 때, for문으로 하는 게 아니라 나눠주자. k는 k를 남은 음식 수로 나눈 나머지요, 바퀴 수는 k를 그 몫이다.
9. 효율성은 통과하나 정확성에서 틀린다.
10. 바퀴 수, 즉 현재 추가적으로 더 먹고 있는 음식의 양은 천장으로 구해야 한다. 2바퀴를 돌 수 있는데 3바퀴는 못 돈다면 무지는 현재 추가적으로 3의 양을 먹으려 하고 있다.

풀이

싸이클의 크기를 최대화 해서 k값을 줄여나가다가
마지막 순간에만 배열을 돌아야 하는 문제다. (배열을 하나하나 도는 것을 최소화하는 것이 관건)

먼저 음식의 양을 카운트하고 이를 양의 오름차순으로 정렬한다.
이 순서대로 해당 음식을 전부 먹어가기 때문이다. (양이 4인 음식은 양이 10인 음식보다 빨리 없어진다)
이를 food_cnt라 하자.

정렬한 후, 그 음식이 모두 비워지게 되는 싸이클의 크기, to_remove를 구한다.
정렬된 배열은 (음식의 양, 등장 횟수)들로 이루어졌다.

i번째로 적은 양의 음식을 모두 먹어버린다고 생각하자.
현재 먹을 음식의 양은 food_cnt[i][0],
그 개수는 food_cnt[i][1],
남은 음식의 수를 food_left라 하자.
그리고 현재 돌면서 여태 먹은 음식의 양을 food_ate라 하자.

to_remove는 현재 to_eat (=지금 먹을 음식의 양) * food_left이다.
to_eat은 food_cnt[i][0] - food_ate이다.
예를 들어, 원래 양이 4인 음식을 끝내버릴 차례인데
여태 음식을 앞에서 각각 2만큼 먹었다고 한다면 지금은 2만큼만 먹어도 그 음식을 모두 먹을 수 있다.

그대로 k값을 줄여나간다. (k -= to_remove)
food_left는 food_cnt[i][1]만큼 줄어들고
food_ate은 to_eat만큼 늘어난다.
food_ate는 여태 먹은 음식의 총합이 아닌 각 음식에서 대해서 먹은 양이라는 것에 주목하자.

만약에 k - to_remove가 음수가 된다면 (해당 음식을 해치우기 이전에 방송이 종료된다면)
그때부터는 사이클의 크기를 남은 음식을 1씩 깎는 주기로 바꾼다.

food_left만큼 깎아나간다면 k를 food_left로 나눈 나머지가 우리가 배열을 돌아야 할 최소 횟수이다.
이렇게 되면 현재 먹고 있는 음식의 양은 k를 food_left로 나눈 몫이며, 나머지가 1이라도 있다면 1을 추가하게 된다.

예를 들자면 만일 k=5이고 food_left가 3이라고 쳤을 때,
무지는 세 음식에 대해서 1씩 먹을 수 있다.
그러고도 모자라 앞의 두 음식에서 1씩 더 먹을 수 있다.
즉 마지막에 방송이 중지됐을 땐, 남은 음식들 중에서 도합 2만큼 먹던 중이던 것이다.
따라서 무지는 ceil(k / 남은 음식의 수)을 추가로 더 먹을 수 있다.
이를 able이라고 하자.
이는 무지가 음식들을 돌면서 먹을 수 있는 최대치이다.

무지가 현재 남은 음식들을 k // 남은 음식의 수바퀴 돌면서 음식을 먹었고,
우리는 미처 다 돌지 못하는 나머지를 직접 돌아보는 것이라고 이해하면 편하다.

이제 k를 1씩 감소시키며 배열을 탐색할 차례이다.
음식이 남았는지 아닌지를 알기 위해선, 배열(food_times)의 원소가 food_ate + able보다 크거나 같은지를 보면 된다.
같다면, 이번 차례에서 다 먹게 되는 음식인 것이다.
크다면, 그렇게 먹어도 아직 다 먹지 못한 음식이다.
작다면 돌기 전에 이미 다 먹은 음식이다.

크거나 같으면 k를 감소시킨다.
그러다 k가 0이 될 때, k초 후 먹을 음식의 인덱스를 반환한다.

만약 위의 전체적인 과정에서 단 한 번도 k값이 음수가 되는 경우가 없다면
이는 k초가 지나면 음식들을 이미 다 먹었다는 말이므로 -1를 반환한다.

밑은 예시를 그림으로 나타낸 것이다.

코드

from collections import Counter
from math import ceil


def solution(food_times, k):
    n = len(food_times)
    
    # food_cnt[i] = (i 번째로 적은 음식의 양, 같은 양을 가지는 음식의 개수)
    food_cnt = sorted(list(Counter(food_times).items()))
    
    # 현재 먹은 각 음식의 양
    food_ate = 0
    
    # 남은 음식 수
    food_left = n

    for i in range(len(food_cnt)):
        # i 번째로 적은 음식의 현재 잔량
        to_eat = food_cnt[i][0] - food_ate
        
        # i 번째로 적은 음식을 아예 비워버리기 위해 지나야 하는 시간
        to_remove = to_eat * food_left

        # 아예 비우진 못한다면
        if k - to_remove < 0:
            # 현재 남아있는 음식들을 돌 수 있는 바퀴 수 = 더 비울 수 있는 각각의 음식의 양
            able = ceil(k / food_left)
            
            # able 바퀴 씩 돌고 남은 k
            k %= food_left

            # 현재 다 먹은 각 음식의 양
            now_eaten = food_ate + able
            
            for l in range(n):
                # 음식의 양이 현재 먹은 양보다 크거나 같다면 (= 아직 남아있다면)
                if food_times[l] >= now_eaten:
                    # k 초 후 먹을 음식 발견
                    if k == 0:
                        return l + 1
                    k -= 1

        # i 번째로 적은 음식을 아예 비워버림
        k -= to_remove
        
        # 지금까지 먹은 각 음식의 양 추가
        food_ate += to_eat
        
        # 남은 음식 개수 줄이기
        food_left -= food_cnt[i][1]

    return -1