[JavaScript] 프로그래머스 - 무지의 먹방 라이브

[문제]

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

프로그래머스

 

[풀이]

문제의 핵심은 이분탐색을 통해 회전판이 몇번째 돌았을 때 k+1초가 되는지 찾아야 합니다.

 

예를 들어 회전판이 [3, 1, 2]이고 k가 5라면 k+1인 6초에 어떤 그릇을 먹는지 찾아야 합니다.

• 1회전 : [2, 0, 1] -> 3초 지남
• 2회전 : [1, 0, 0] -> 5초 지남
• 3회전 : [0, 0, 0] -> 6초 지남

따라서 3회전에 6초가 포함되어 있으므로 3회전을 검색하여 1번 그릇을 먹는것을 구할 수 있습니다.

 

 

이분탐색을 사용하여 k+1이 포함된 회전을 찾는 과정은 다음과 같습니다.

 

초기 세팅

• 최소 회전수 left = 1;
• 최대 회전수 right = 6; (모든 그릇의 총합 = 3 + 1 + 2)

이분탐색 과정

• mid = (left + right)/2 = 3 => 3회전 소요 시간은 6이므로 right = 2 로 갱신 
• mid = 1 이므로 1회전 소요 시간은 3이므로 left = 2로 갱신
• mid = 2 이므로 2회전 소요시간은 5이므로 left = 3으로 갱신
• 이분탐색이 종료되고 left = 3이므로 3회전시 우리가 찾는 k+1이 포함

따라서 left - 1 (2) 회전이 끝난후 시간은 5초이고, 2회전이 끝난후 회전판의 음식 상태 food배열은 다음과 같습니다.

[ [ 3, 1 ] ]

 

따라서 6초일때는 1번 회전판을 먹게됩니다.

 

[코드]

function solution(food_times, k) {
    var answer = -1;
    let sum = food_times.reduce((acc, cur) => acc + cur);
    if(sum < k) {
        return answer;
    }
    
    // 최소 rotate 1, 최대 rotate 6
    let left = 1;
    let right = sum;
    while(left <= right) {
        let mid = Math.floor((left + right)/2);
        let time = 0;
        food_times.forEach((i) => {
            if(i <= mid) {
                time += i;
            } else {
                time += mid;
            }
        });
        if(time < k+1) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    let time = 0;
    left--;
    food_times.forEach((i) => {
        if(i <= left) {
            time += i;
        } else {
            time += left;
        }
    });
    let foods = food_times.map((i, idx) => [i, idx+1]).filter((i) => i[0] > left);
    for(let i=0;i<foods.length;i++) {
        time++;
        if(time === k+1) {
            answer = foods[i][1];
            break;
        }
    }
    return answer;
}