문제 개요

문제: 공유기 설치

분류: 이분 탐색, 매개 변수 탐색

난이도: 골드4

문제 풀이

이분탐색을 통해 두 공유기 사이의 최대 거리를 구한다.

이분탐색을 진행하기 위해 먼저 집 좌표를 오름차순으로 정렬한다.

이후 left와 right에 각각 집 사이의 최소 거리, 최대 거리를 저장하고 left가 right보다 작거나 같은 동안에 아래를 반복한다.

1. 두 변수의 중간 값인 mid 이상의 거리를 가진 집들에 공유기를 설치해본다.
2. 설치한 공유기의 개수가 설치하려던 공유기의 개수 C보다
   • 동일하거나 더 많게 설치되면 정답 변수에 mid를 저장하고 거리를 늘린다.
     즉, left에 mid+1을 대입한다.
   • 더 적게 설치되면 거리를 줄인다.
     즉, right에 mid-1을 대입한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [NC, ...home] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, C] = NC.split(" ").map(Number);
home = home.map(Number);

const binarySearch = () => {
  // left와 right에 각각 집 사이의 최소 거리, 최대 거리를 저장한다.
  let [left, right] = [1, home[N - 1] - home[0]];
  let result = 0;

  while (left <= right) {
    let mid = ~~((left + right) / 2);

    let idx = 0;
    let count = 1;
    // mid 이상의 거리를 가진 집들에 공유기를 설치해본다.
    for (let i = idx + 1; i < N; i++) {
      if (home[i] - home[idx] >= mid) {
        idx = i;
        count++;
      }
    }

    // 설치하려는 공유기 개수와 동일하거나 더 많게 설치되면
    if (count >= C) {
      result = mid;
      left = mid + 1; // 거리를 더 늘린다.
    } else {
      right = mid - 1; // 거리를 더 줄인다.
    }
  }

  return result;
};

const solution = () => {
  home.sort((a, b) => a - b);
  console.log(binarySearch());
};

solution();