2019 KAKAO 코딩테스트 무지의 먹방 라이브

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

코딩테스트 연습 - 무지의 먹방 라이브

 

Naive 하게 풀면 하나씩 음식을 먹어가면서 계산하면 된다. 하지만, 해당 방식으로는 효율성 문제에서 시간초과가 날 것이라고 생각했다.

내가 중요하게 생각했던 것은 "사라지는 음식"이었다.
1. 값이 작은 음식들부터 소진되고, 음식들은 자신보다 작은 음식들보다 늦게 소진된다.
2. 음식들이 전부 소진되는 시점은 회전판의 회전수가 "음식의 값"일 때다.

이를 고려하여 계산해본다면, i 번째 loop 에서 소모되는 음식 총량은 다음과 같다.

    음식 값을 기준으로 정렬되있다고 한다면
       $$ \sum_{n=0}^{i} (arr[n]-n) * (len(arr) - n) $$

이를 바탕으로, 다음으로 먹어야하는 음식이 소모되는 loop와 그 전 loop까지 먹은 음식의 총량(b)을 구한 뒤, (k - b) % (남은 음식의 수) 를 해준다면, 다음으로 먹어야하는 음식을 구할 수 있다. 이는, data에 음식의 값 뿐만 아니라 음식의 기존 idx를 저장해야 구할 수 있다.

나는 (음식 값, 음식 idx) 를 tuple로 저장했다.

def solution(food_times, k):
    answer = 0
    
    if sum(food_times) <= k: return -1
    
    arr = [[f, idx+1] for idx, f in enumerate(food_times)]
    arr.sort()
    
    b = c = i = loop = 0
    l = len(food_times)    
    
    for idx in range(len(arr)):
        c += (arr[idx][0] - loop) * l
        l -= 1
        loop = arr[idx][0]
        if c > k:
            i = idx
            break
        b = c
        
    n = sorted(arr[i:], key = lambda x: x[1])
    k -= b
    k %= len(n)

    return n[k][1]