[알고리즘-JS] 마구간 정하기 - 결정 알고리즘

문제

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

 

입력 예제

5 3

1 2 8 4 9

 

출력 예제

3

 

 

풀이

// mid를 거리로 정하면 몇 마리의 말이 들어갈 수 있는가
function count (stable, dist) {
  let cnt = 1, ep=stable[0]; // 한 마리를 가장 왼쪽에 우선 배치
  for (let i = 1; i<stable.length; i++) {
    if (stable[i] - ep >= dist) { // 말의 거리가 dist보다 크거나 같은가
      cnt++;
      ep=stable[i];
    }
  }
  return cnt;
}

function solution(c, stable) {
  let answer = 0;
  stable.sort((a, b) => a - b);
  let lt = 1; // 마구간 사이 거리는 좌표에 상관 없이 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;
}