무지의 먹방 라이브

• food_times를 오름차순으로 정렬한 배열을 f라고 하자. 음식의 갯수는 n이라고 하자.
• 처음에는 모든 음식이 아직 남아있다. n개의 음식을 f[0]만큼씩 먹고 나면, 이제 남은 음식의 갯수는 n-1이 된다. 이제 n-1개의 음식을 f[1]-f[0]만큼씩 먹고 나면, 남은 음식의 갯수는 하나 줄어서 n-2가 된다.
• 이렇게 시간을 더해 나가면서 K보다 커지는 시간을 찾으면, 음식이 몇개 남았을때 K 시간이 되는지 알 수 있다.
  • 다시 말하면, 아래를 만족하는 i를 찾는다
    • n*f[0] + (n-1)(f[1]-f[0]) + … + (n-i)(f[i]-f[i-1]) ≤ K < n*f[0] + (n-1)(f[1]-f[0]) + … + (n-i-1)(f[i+1]-f[i])
• 이 말은, 음식이 n-i개 남은 시점에서 남은 시간이 K-f[i]라는 의미이니, n-i 개의 남은 음식 중, (K-f[i])%(n-i) 번째의 음식의 번호를 출력하면 된다.
• 처음 food_times를 정렬하는데에 O(nlogn)이 걸리고, i를 구하는 데는 O(n)이 걸린다. 그래서 총 시간 복잡도는 O(nlogn)

"""Solution code for "Programmers 42891. 무지의 먹방 라이브".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42891
- Solution link: http://www.teferi.net/ps/problems/programmers/42891
"""


def solution(food_times, k):
    answer = -1
    food_count = len(food_times)
    time_and_nums = sorted((t, i) for i, t in enumerate(food_times))    
    is_remaining = [True] * food_count
    remaining_food_count = food_count
    remaining_time = k
    prev_time = 0
    for cur_time, num in time_and_nums:
        spent_time = remaining_food_count * (cur_time - prev_time)
        if spent_time > remaining_time:
            remaining_foods = [i for i in range(food_count) if is_remaining[i]]
            answer = remaining_foods[remaining_time % remaining_food_count] + 1
            break
        is_remaining[num] = False
        remaining_food_count -= 1
        remaining_time -= spent_time
        prev_time = cur_time

    return answer