마구간 정하기(결정알고리즘)

문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드)

 

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

 

▣ 출력설명
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

▣ 입력예제 1

5 3

1 2 8 4 9

 

▣ 출력예제 1

3

 

Tip

 

문제풀이

//내가 작성한 답
function count(arr,distance){  //5
    let endPoint = arr[0];
    let cnt = 1;
    for(let i = 1 ; i < arr.length ; i++){
        if(arr[i]-endPoint >= distance){
            cnt++;
            endPoint = arr[i];
        }
    }
    return cnt;
}


function solution(arr,horses){
    let answer = 0;
    arr.sort((a,b) => a-b);

    let lt = 1; // 마을 배치할 수 있는 최단 거리는 1임
    let rt = Math.max(...arr); // 배열의 가장 큰 값을 그냥 넣음
    console.log('lt',lt);
    console.log('rt',rt);

    while(lt <= rt){
        let mid = Math.floor((lt+rt)/2);
        if(count(arr,mid) >= horses){ //필요한 마리수 만큼 제대로 배치가 된 경우임, 거리를 늘려야함
            if(mid > answer) answer = mid;
            lt = mid+1;
        }else{ //필요한 마리수 만큼 제대로 배치가 되지 않은 경우임, 거리를 줄여야함
            rt = mid-1;
        } 
    }

    return answer;
}


let arr = [1,2,8,4,9];
console.log(solution(arr,3));