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

문제

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

제한사항

입출력 예

풀이

function count(stable, dist) {
  let cnt = 1,
    ep = stable[0]; // 첫번째 말은 항상 가장 앞
  for (let i = 1; i < stable.length; i++) {
    // 다음 말과 현재말의 차이가 dist보다 크면 말을 배치
    if (stable[i] - ep >= dist) {
      cnt++;
      ep = stable[i];
    }
  }
  return cnt;
}
function solution(c, stable) {
  let answer;
  stable.sort((a, b) => a - b);
  let lt = 1;
  let rt = stable[stable.length - 1];
  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2);
    if (count(stable, mid) >= c) {
      // 거리를 mid로 두었을 때 배치할 수 있는 말이 c마리보다 많다 그럼 거리를 늘려야 배치할 수 있는 말이 줄어든다.
      answer = mid;
      lt = mid + 1; // 범위를 더 크게 만들어서 결과적으로 다음 루프에 mid값은 높아질 것이다.
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}

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

우선 sort, stable 배열은 말의 위치를 순서 없이 저장한 배열이기 때문에 sort를 해도 상관이 없다.

lt의 경우 헷갈릴 수 있는데 거리를 나타낼 것 이기 때문에 그냥 1로 하는 것이다. rt는 stable에 가장 큰 값을 넣으면 된다.

count 함수는 거리가 주어졌을 때, 그 거리로 말을 배치하면 몇 마리의 말이 배치되는지 세어주는 함수이다.

거리가 커질 수록 배치하는 말의 수는 줄어든다.

dvd 문제와의 차이점을 잘 생각해야한다. 이 문제는 최대값을 원하는 문제이다. 따라서 조건이 count함수의 리턴 값이 c보다 크거나 같은 경우가 된다. 그럼 mid에 c가 될 수 있는 가장 큰 값이 올 것이다.