[백준 2110] 이분 탐색 - 공유기 설치

✨ 정답 ✨

// const { json } = require("express/lib/response");
// const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

// const fs = require('fs');
// let input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

let [N, C]=input.shift().trim().split(' ').map((el)=>+el)
// 주어진 집 좌표를 배열로 만들고 오름차순으로 정렬
let houseArray=input.map((el)=>+el.trim()).sort((a,b)=>a-b)


let left =0;
let right=houseArray[N-1]
// 가장 인접한 두 공유기 사이의 최대 거리를 담을 answer 변수 선언
let answer=0;

// 라우터 설치 가능 여부 확인
const routeAble=(distance)=>{
  let count=1;
  let lastRoute=houseArray[0];
  for (let i=1;i<N;i++){
    if (houseArray[i]-lastRoute>=distance){
      count+=1;
      lastRoute=houseArray[i];
    }
  }
  return count>=C;
}

// 이분 탐색을 통해 가능한 최대 거리를 찾음
while(left<=right){
  let middle=Math.floor((left+right)/2);
  if (routeAble(middle)){
    answer=middle;
    left=middle+1;
  }else{
    right=middle-1;
  }
}
console.log(answer)

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

이분 탐색 과정 중 middle이 라우터를 설치할 수 있는 곳인지 확인해야 한다.