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

< 문제 >
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

풀이
이분탐색을 이용하기위해 배열을 먼저 정렬한다.
lt를 1부터 rt를 배열의 가장큰값으로 잡고 이분탐색을한다.
while문을 돌면서 (rt + lt) / 2를 소수점 내림으로 구한 이후 해당 값을 이용해서
count 함수를 호출한다.
count 함수는 처음 하나는 무조건 존재하니 cnt= 1 , endpoint는 첫번째 배열로잡고
index 0인 첫번째는 이미 구했으니 1부터 stable길이만큼 반복한다.


stable[i] - endpoint가 mid값 보다 크거나같을때 cnt를 추가하고,
endpoint에 조건에 맞는 stable[i]를 대입하고 반복한다.
count 함수는 cnt변수를 return하고 count함수가 c인 3보다 크거나 같을때는 조건에 맞으니 answer에 mid값을 넣어주고 lt값에 mid + 1값을, 반대의 경우 rt값에 mid - 1값을 대입해서 이분탐색해가며 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력한다.

// 마구간 정하기(결정알고리즘)
function count(stable, dist) {
  let cnt = 1;
  let endpoint = stable[0];
  for (let i = 1; i < stable.length; i++) {
    if (stable[i] - endpoint >= dist) {
      cnt++;
      endpoint = stable[i];
    }
  }
  return cnt;
}

function solution(c, stable) {
  let answer = 0;
  stable.sort((a, b) => a - b);
  let lt = 1;
  let rt = stable[stable.length - 1];
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(stable, mid) >= c) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }

  return answer;
}

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