프로그래머스 - [Level 4] 징검다리(JAVASCRIPT)

프로그래머스 징검다리

카테고리 : 이분탐색

이분탐색은 이분탐색할 기준을 어떻게 잡는지가 중요하다.
이번 문제에서는 이분탐색의 기준을 '거리의 값'으로 잡았다.

이 거리의 값을 기준으로 삭제해야 할 바위가 결정된다.
---------------------------------
시작                          끝
[0,  2,  11,  14,  17,  21 , 25]
---------------------------------
이분탐색의 시작값은 가장 작은 위치의 값과 가장 큰 위치의 값인 [start,end]=[0,25] 이다.
따라서, 초기 거리 기준 값은 (0+25)/2= 12 가 된다.

이제, rocks 배열을 돌며 삭제 처리를 해줘야한다.

두 바위의 거리가
1) 기준 거리의 값보다 작은 위치의 바위는 삭제해준다.(count 처리)
2) 기준 거리의 값보다 크다면 현재 바위의 위치(now) index를 변경한다.

예를들어, 기준거리의 값이 12이고, 삭제가능한 바위(n)이 2개라고 해보자.
그리고 아래는 rocks 배열이다.

rocks=[0,  2,  11,  14,  17,  21 , 25]

현재 바위의 위치를 now 라고 하고 배열을 탐색해보자.(0부터 시작)
-------------------------------------------------------
rocks[1] - now = 2 - 0, 삭제가능 => count+1
남은 바위 [0,  11,  14,  17,  21 , 25]

rocks[2] - now = 11 - 0, 삭제가능 => count+1
남은 바위  [0,  14,  17,  21 , 25]

rocks[3] - now = 14 - 0, 삭제불가 => now=rocks[3]
남은 바위 [0,  14,  17,  21 , 25]

rocks[4] - now = 17 - 14, 삭제가능 => count+1
남은 바위 [0,  14,  21 , 25]

rocks[5] - now = 21 -14, 삭제가능 => count+1
남은 바위 [0,  14,  25]

rocks[6] - now = 25 -14, 삭제불가 => now=rocks[6]
남은 바위 [0,  14,  25]
-------------------------------------------------------
기준 거리 값이 12일 때 count의 값은 4 가 되고 n보다 큰 값이므로
기준 거리 값이 더 작은경우를 탐색할 수 있다.
end=mid-1 로 처리해주고 위를 반복하면 답이 도출된다.
(그 반대의 경우에는 start=end+1 이 된다.)


거리의 값이 4인 경우를 보면
rocks=[0,  2,  11,  14,  17,  21 , 25]
-------------------------------------------------------
rocks[1] - now = 2 - 0, 삭제가능 => count+1
남은 바위 [0, 11,  14,  17,  21 , 25]

rocks[2] - now = 11 - 0, 삭제불가 => now=rocks[1]
남은 바위  [0, 11, 14,  17,  21 , 25]

rocks[3] - now = 14 - 11, 삭제가능 => count+1
남은 바위 [0, 11, 17, 21 , 25]

rocks[4] - now = 17 - 11, 삭제불가 => now=rocks[4]
남은 바위 [0, 11,  17,  21 , 25]

rocks[5] - now = 21 - 17, 삭제불가 => now=rocks[5]
남은 바위 [0, 11,  17,  21 , 25]

rocks[6] - now = 25 - 21, 삭제불가 => now=rocks[6]
남은 바위 [0, 11,  17,  21 , 25]
-------------------------------------------------------
총바위의 개수 - 남은바위 = 2를 만족하므로 조건에 부합하는
최소 거리값 중 최대가 된다.

소스 코드

function solution(distance, rocks, n) {
    let answer = 0;
    rocks=[0,...rocks.sort((a,b)=>a-b),distance];
    
    const BinarySearch=()=>{
        let start=0;
        let end=rocks[rocks.length-1];
        
        while(start<=end){
            let mid=Math.floor((start+end)/2);
            let count=0,now=0;
            for(let i=1;i<rocks.length;i++){
                if(rocks[i]-now<mid){
                    count++;   
                }else{
                    now=rocks[i];
                }
            }
            
            if(count>n){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        answer=end;
    }
    
    BinarySearch();
    return answer;
}