📌 문제 설명

공유기 설치 보기

📌 문제 접근

1. 이분 탐색 인지 알아내기

이것도 문제 지문에 대놓고 있는 경우가 있다. 보통 아래 3개 중에 2개정도? 있으면 이분 탐색일 확률이 높다.

• 문제의 제한 사항이 억 이상 : JavaScript의 for문으로 1억번 돌면 대충 1초가 걸린다. 따라서 시간 초과일 수 있기 때문에 이분 탐색일 확률이 높다.
• 최댓값의 최솟값, 최솟값의 최댓값 : "가장 인접한 두 공유기 사이의 거리(최솟값)를 최대로(최댓값)해라", "모든 사람이 심사를 받는 시간(최댓값)의 최솟값을 구해라." 이런 결과를 원하면 이분 탐색일 확률이 높다.
• 직접 구하기는 힘든데, 검증은 너무 쉬울 때 : 모든 조합 다짜야할 것 같은 막막함. 정답을 가정하고 검증하는 방식이 쉬우면 이분 탐색일 확률이 높다.

2. 이분 탐색의 갱신 위치

이런 문제를 풀다 보면 answer = mid를 어디에 붙여야 하나 생각이 들곤 한다. 기계적으로 = 붙은 곳에 넣는게 아니라, 문제의 목표(최댓값 or 최솟값)에 따라 달라진다. 원하는 조건(성공 상태)을 만족 했을 때 킵 해두는게 정석이다.

📌 내가 작성한 코드

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split(/\s+/).map(Number);

const [n, c, ...wifi] = input;
wifi.sort((a, b) => a - b);
let [min_length, max_length, answer] = [0, wifi.at(-1) - wifi[0], 0];

while (min_length <= max_length) {
  const mid = Math.floor((max_length + min_length) / 2);
  let [count, before_wifi_idx] = [c - 1, 0];
  for (let i = 1; i < n; i++) {
    if (count === 0) break;
    if (wifi[i] - wifi[before_wifi_idx] >= mid) {
      count--;
      before_wifi_idx = i;
    }
  }
  if (count === 0) {
    answer = mid;
    min_length = mid + 1;
  } else {
    max_length = mid - 1;
  }
}
console.log(answer);

📌 시간 복잡도

• 이분 탐색: O(log(max_length - min_length)) = O(log(N))
• 각 mid 값 검증: O(n)
• 전체 시간 복잡도: O(n × log(N))

📌 참고 링크

• Array.prototype.sort()

• Math.floor()

• Array.prototype.at()

• 이분 탐색(Binary Search)