무지의 먹방 라이브

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

프로그래머스

처음에는 음식을 순회하면서 O(N^2) 문제를 접근했다.
N = 음식, N = 시간

음식은 Set 에 등록하여 다 먹은 음식은 Set 에서 제거하는 방법으로 마지막 음식 ( t + 1 ) 의 index 를 구하여 정확성 테스트를 통과했지만, 효율성 테스트에서는 실패했다.

 

고민을 하다.. 다른 사람의 아이디어를 도움 받아 n 초 만큼의 음식을 먹는 과정을 O(1) 로 줄일 수 있었다.

아이디어는 음식의 양을 정렬하여 n 초의 시간을 한번에 빼는 방법이다.

 

위 아이디어를 쓰기 위해서는 최초의 음식 index 와 음식 time 을 관리하는 dict 가 필요하고

n 초가 흐른 시점에 한번에 먹을 수 있는 m 초를 구해야한다.

 

동시에 먹을 수 있는 음식이 남은 시간 보다 작다면 현 시점에 남아 있는 음식의 index 를 원본 음식 index 로 정렬하여 구하면 된다 ( 처음에 음식 양으로 정렬을 했기에 다 먹은 음식은 자동으로 index 에서 벗어난다 )

function solution(food_times, k) {
    var foods = food_times.map((time, idx) => ({ index: idx + 1, time }));
    // ascending
    foods.sort((a, b) => a.time - b.time);

    var n = food_times.length;
    var pretime = 0;
    for(var i = 0; i < n; i++) {
        var spend = (foods[i].time - pretime) * (n - i);
        if(spend == 0) continue;
        
        if(spend <= k) {
            k -= spend;
            pretime = foods[i].time;
        } else {
            k = k % (n - i);

            var temp = [];
            for(var j = i; j < n; j++) {
                temp.push(foods[j].index);
            }
            temp.sort();

            return temp[k];
        }
    }
    return -1;
}