[JavaScript/section 7] 12 - 마구간 정하기

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

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, ..., xN의 좌표를 가지며, 마구간간에 좌표과 중복되는 일은 없습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력해보자!

입력설명

첫 줄에 자연수 N과 C가 공백을 사이에 두고 주어진다.

둘째 줄에 마구간의 좌표가 차례로 주어진다.

출력설명

첫 줄에 가장 가까운 두 말의 최대 거리를 출력한다.

입력예제
5 3
1 2 8 4 9

출력예제
3

 

👍 풀이 방법

가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 구하는 문제이다. 마구간에 말 3마리를 배치할 수 있는 경우는 한가지 이상이지만 그 중에서 가장 가까운 두 말의 거리가 최대가 되는 최적의 값을 구해야한다는 것이다. 특정한 상황에서 최적의 값을 구해야 하므로 이분 탐색을 이용한 파라메트릭 서치 알고리즘을 사용하면 된다. 이 문제를 풀며 느낀 점은 파라메트릭 서치 알고리즘을 사용할 때는 주어진 일련의 값들이 아니라 주어진 범위에 포커스를 맞춰서 풀어야 된다는 것이다.

• 마구간의 좌표를 오름차순으로 정렬한다.
• lt(말 사이의 최소 거리)를 1로 초기화한다. stable[0] 값이 1이 아닌 경우엔 원하는 답을 얻지 못하게 되므로 stable[0]으로 초기화해서는 안된다. 
• rt(말 사이의 최대 거리)를 배열의 마지막 값으로 초기화한다.
• mid(가장 가까운 말 사이의 거리)를 Math.floor((lt + rt) / 2)로 초기화한다. (이분 탐색)
• count() 함수는 mid(가장 가까운 말 사이의 거리)를 인자로 받아 말 사이의 거리에 따라 마구간에 몇마리의 말이 배치될 수 있는지를 리턴해준다. mid가 작을 수록 더 많은 말이 배치될 수 있다.
• count() 함수에서 리턴되는 값이 3보다 크거나 같다면 조건에 만족하므로 answer에 mid를 저장한다. 그리고 최대값을 구하고 있기 때문에 mid 이하의 값들은 탐색에서 제외된다. lt = mid + 1
• 리턴되는 값이 3보다 작다면 mid 이상의 거리들 또한 3마리 이상의 말들이 배치될 수 없으므로 탐색에서 제외된다. rt = mid - 1

 

📝 소스코드

function count(stable, dist) {
  let cnt = 1;
  //첫 번째 좌표에 말 배치
  horse = stable[0];

  for (let i = 1; i < stable.length; i++) {
    // 해당 위치에서 말의 처음 위치를 뺏는데 현재 정해진 가장 가까운 말 사이의 거리(dist)보다 크거나 같다면 cnt++
    // 말의 위치를 해당 위치로 변경하여 말을 더 배치할 수 있는지 계속해서 비교
    if (stable[i] - horse >= dist) {
      cnt++;
      // 말 재배치
      horse = stable[i];
    }
  }

  return cnt;
}

function solution(c, stable) {
  let answer;
  stable.sort((a, b) => a - b);
  // lt - 말 사이의 최소 거리, rt - 말 사이의 최대 거리
  let lt = 1,
    rt = stable[stable.length - 1];

  while (lt <= rt) {
    // mid - 가장 가까운 말 사이의 거리
    let mid = Math.floor((lt + rt) / 2);
    // 배치할 수 있는 말의 개수가 c보다 크거나 같다면 lt의 크기를 늘려서 탐색
    // c보다 작다면 rt의 크기를 줄여서 탐색
    if (count(stable, mid) >= c) {
      answer = mid;
      // 더 좋은 답을 찾기 위해서
      lt = mid + 1;
    } else rt = mid - 1;
  }

  return answer;
}

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