프로그래머스 : 무지의 먹방 라이브 JavaScript

각각의 들어있는 음식의 양을 막대형 그래프로 표현해 본다면

 

O
O		O
O	O	O

 

이것을 크기가 작은 순으로 정렬하다면 

 

		O
	O	O
O	O	O

 

큰것 부터 먹더라도 k값이 전체 음식의 수보다 앞선다면은 사이클 한번이 돌고나서는  남은 K수는 K-len(음식의 수)가 될것이고 그래프의 모양은 다음과 같이된다.

 

		O
	O	O

이것에서 아이디어를 얻어서 문제를 풀면 다음과 같은 코드가 된다.

 

추가팁으로는 1~n 차례대로 음식을 순회하기 때문에 index순서대로 뽑아야한다

(문제에서는 다음 음식에 가장 많이 남은 음식을 선택한다고했다. 예를들어 5번 음식을 뽑앗으면 6~N, 1~4번중 가장 많이 남은것을 뽑는 다는 뜻 따라서 다음과 같이 index로 정렬하면 정답이 나온다.)

function solution(food_times, k) {
    var cnt = 0;
    var foods = food_times.map((time, index) => {
        cnt += time;
        return [time, index + 1];
    }).sort((a, b)=> {
        return a[0] - b[0];
    });

    if(cnt <= k)
        return -1;

    var len = foods.length;
    var minus = 0;
    let i =0;
    for(i=0; i<len; i++){
        let tmp = len - i;     
        let f = foods[i][0] - minus;

        if(k - tmp * f >= 0) {
            minus += f;
            k -= tmp * f;
        }else {
            let gab = Math.floor(k / tmp);
            k -= gab * tmp;
            break;
        }
    }

    const answer = foods.slice(i,len).sort((a, b) => a[1] - b[1]);

    return answer[k][1];
}

console.log(solution([3, 6, 6],1));