[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT / python

음식을 개수만큼 쌓아놨다고 생각해보자.

모든 음식을 다 먹는다고 할 때 음식을 쭉 세워놓은 상태에서 음식 중에 가장 높이가 작은 음식의 높이만큼 모든 음식들을 한꺼번에 제거하면서 빠르게 줄여나갈 수 있다.

예를 들면 5개의 음식이 1번 음식부터 차례대로 6, 5, 2, 2, 7개 쌓아져 있다고 할 때 65227 -> 43005 -> 10002 -> 00001 -> 00000 순서가 될 것이다.

이제 네트워크 장애가 난 k초까지 음식을 먹다가 네트워크가 정상화되고 남아있는 음식 중 어떤 음식을 먹을 지를 알아내면 된다.

위의 6, 5, 2, 2, 7개의 음식들을 각각 인덱스 정보와 함께 (6,0), (5,1), (2,2), (2,3), (7,4) 묶어주고 음식 개수의 오름차순으로 정렬해주면 (2,2), (2,3), (5,1), (6,0), (7,4) 가 된다.

정렬된 리스트를 보면 인덱스를 올리면서 위에서 설명했던 것처럼 음식들을 한꺼번에 제거할 수 있다.
예를 들어 k가 13이라고 할 때 처음에 음식들을 한꺼번에 제거하는 경우를 보면 (2,2) (2,3) || (5,1) (6,0) (7,4) 가장 높이가 작은 음식 개수인 2개에 맞춰 모든 음식들을 제거하면 10개의 음식을 제거하게 된다.

그리고 k에 방금 제거한 10을 빼준다. 그리고 위의 방법을 다시 반복하는데 여기서 좀 전에 제거한 최소 음식 개수인 2개를 변수 하나에 기억해둔다. 왜냐하면 정렬된 리스트의 인덱스가 다음 최소 음식 개수인 5개에 도달했을 때 5개에 맞춰 모든 음식들을 제거하면 안되고 이미 좀 전에 모든 음식을 2개씩 제거했기 때문에 5 - 2 = 3을 제거해주면 된다.

이 때 반복하면서 제거를 하기 전에 제거했을 때 k가 0보다 작아질 경우를 항상 확인하고 제거해야 한다. 왜냐하면 방금 말한 경우에 남아있는 음식들 중에서 남은 k 순서에 먹게될 음식의 번호가 답이 되기 때문이다.

def solution(food_times, k):
    answer = -1

    food_infos = [(time, idx) for idx, time in enumerate(food_times)]
    food_infos.sort()

    before_time = 0
    for idx, food_info in enumerate(food_infos):
        time, _ = food_info

        if time == before_time:
            continue

        if k - (len(food_infos) - idx) * (time - before_time) < 0:
            last_lefted_food_infos = sorted(food_infos[idx:], key=lambda x: x[1])
            last_lefted_food_idx = last_lefted_food_infos[k % len(last_lefted_food_infos)][1] 

            return last_lefted_food_idx + 1

        k = k - (len(food_infos) - idx) * (time - before_time)
        before_time = time

    return answer