프로그래머스 - [Level 4] 무지의 먹방 라이브(JAVASCRIPT)

프로그래머스 무지의 먹방 라이브[2019 카카오 블라인드]

카테고리 : 시뮬레이션

전형적인 시뮬레이션 문제다. 배열의 shift()의 시간복잡도를 생각못하고
애먹었던 문제였다.

풀이과정은 아래와 같다.
핵심적인 아이디어는
"k(초) - (가장 작은 음식의 양 * 현재 남은 음식의 갯수)"로
k 값을 제거해나가는 것이다. 

이때, 매번 모든 음식의 양은 가장 작은 음식의 양씩 줄어들기 때문에 
(실제로 로테이션을 돈것이나 마찬가지이기에)
이 음식값을 누적해 계산해줘야한다.

----------------------------------------------------
[5 7 8 2 3 3 3 2] 가 초기 food_times배열이라면
가장 최소 음식의 양인 2를 기준으로 한번의 로테이션을 돌면
[3 5 6 0 1 1 1 0] 이 된것이나 마찬가지라고 생각하면 된다.
----------------------------------------------------

따라서, 다시 식을 정리하면

"k(초) - (가장 작은 음식의 양 - 현재 누적된 음식의 양) * (현재 남은 음식의 갯수)"
가 된다.

k의 값이 현재 남은 음식의 갯수보다 작을 때까지 무한반복한다.

이후 반복문을 빠져나오면 음식의 양이 0인 음식은 제거해주고
배열의 k+1 번째 값의 index를 리턴하면 답이된다.


1) 큐에 [food_time,index]의 형식으로
food_time을 기준으로 오름차순 정렬해 food_times의 원소를 넣어준다.

2) k 의 값을 제거해나간다.
idx : 현재 위치
count : 누적 음식 양
sum : 현재(idx) 음식의 양 - 누적 음식 양
queue.length-idx : 현재 남은 음식의 갯수

* k(초)를 제거해준다.

k - = (queue.length - idx) * sum;

* 다먹어 치운 음식은 0 으로 만들어준다.
이때, queue를 shift() 해주면 시간초과가 발생한다.
배열의 삭제(shift())는 최악일 때, O(N)의 시간복잡도가 발생하기때문이다.
따라서 queue.shift()가 아닌 idx를 활용해 queue[idx][0]=0 으로 치환해주며,
문제를 풀이해야한다.

if(queue[idx][0]-count===0){
	queue[idx][0]=0;
	idx++;
}

3) 음식의 값이 0이면 제거해주고 인덱스 순으로 정렬해준다.
이때 큐의 k+1 번째 값의 인덱스를 리턴하면 답이 된다.

소스 코드

function solution(food_times, k) {
    let count=0;
    let queue=food_times.map((a,b)=>[a,b]).sort((a,b)=>a[0]-b[0]);
    const total = food_times.reduce((a,b)=>{return a+b},0);
    if(total<=k) return -1;
    
    let idx=0;
    while(queue.length-idx){
        let sum=queue[idx][0]-count;
        if(k-(queue.length-idx)<0) break;
        while(k-(queue.length-idx)*sum<0)
            sum--;
        
        k-=(queue.length-idx)*sum;
        count+=sum;
        while(true){
            if(queue[idx][0]-count===0){
                queue[idx][0]=0;
                idx++;
            }else{
                break;
            }
        } 
    }
    queue=queue.filter((a,b)=>a[0]>0).sort((a,b)=>a[1]-b[1]);
    return queue[k][1]+1;
}