결정 알고리즘(이분탐색) - 공유기 설치

흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제이다.

이전 문제인 뮤직 비디오의 심화버전이라고 생각하면 된다.

이분 탐색을 사용하여 가장 최적의 답을 구하는 방법은 같지만 최적의 조건을 찾는 과정이 조금 더 까다롭게 제출된 거 같다.

문제 (백준 2110)

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

---

📝풀이과정

구하고자 하는 것은 가장 인접한 두 공유기 사이의 최대 거리이다.

이것을 이분탐색으로 효율적으로 빠르게 구하면 된다.

가장 인접한 두 공유기 사이의 최소 거리를 lt로 지정하고 최대 거리 그 이상의 값을 rt로 지정한다.

집들 중 가장 먼 거리에 위치한 곳은 예시에서 9이다. 따라서 집에 공유기를 설치할 때 두 공유기 사이의 거리는 9를 넘지 않을 것이다. 적절한 거리가 될 수 있는 값을 지정해야한다.

이 때 집들의 위치는 오름차순 정렬을 해야한다. 수직선 상에 차례대로 위치하고 있기 때문이다. 정렬이 되어야 두 집 사이의 거리를 올바르게 구할 수 있다.

lt = 1, rt = homes[homes.length -1] = 9

 

그 다음에 중간값을 구해서 그 값만큼 집 들 사이의 간격을 두고 공유기를 설치할 때, 몇 개의 집에 설치할 수 있는지를 확인한다.

mid = Math.floor((lt+rt)/2) = 5

 

가장 인접한 두 공유기 사이의 최대거리를 구해야하기 때문에 맨 첫번째 집부터 공유기를 설치한다고 가정한다.

공유기 사이의 거리가 최소 5만큼은 유지해야한다. 5보다 거리가 작으면 공유기를 설치할 수 없다. 우리는 최대거리를 구해야하기 때문이다. 다른 말로 두 집 사이의 거리가 5보다 크면 공유기 설치는 가능하다.

인접한 공유기 사이의 거리가 최소 5일 때는 다음과 같이 2개의 집에 설치할 수 있다.

 

1 2 4 8 9

 

나는 3개의 공유기를 설치해야한다. 5만큼 간격을 둘 때는 2대밖에 설치하지 못하니 간격을 줄여야한다.

다시 적절한 거리를 탐색해야한다. 이분 탐색을 이용해서 5미만의 범위에서 적절한 값을 찾는다.

즉, mid 값이 적절한 답이 될 수 있는지 계속 확인하는 것이다.

lt = 1, rt = mid - 1 = 4, mid = 2

 

다시 위의 과정을 수행하면 다음과 같이 공유기가 배치된다.

 

1 2 4 8 9

 

이번에는 3대를 모두 설치했다. 하지만 최대 거리를 구해야하기 때문에 적절한 답인지 더 탐색해보아야한다.

이 때는 2 초과의 범위에 적절한 값이 존재하는지 확인한다.

 

lt = 3, rt = 4, mid = 3

배치 결과 ➡ 1 2 4 8 9 

이번에도 모두 설치가능하다. 더 탐색해보자.

 

lt = 4, rt = 4, mid = 4

배치 결과 ➡ 1 2 4 8 9 

이번에는 2대 밖에 설치못한다. 모두 탐색을 완료했고 가장 최대 거리는 3이 되므로 정답은 3이다.

---

🛠코드

let [x, ...homes] = require('fs').readFileSync(0).toString().trim().split('\n');
homes = homes.map(Number);
const c = Number(x.split(' ')[1]);

function count(homes, d) {
  let ep = homes[0];
  let cnt = 1;
  for (let i = 1; i < homes.length; i++) {
    if (homes[i] - ep >= d) {
      cnt++;
      ep = homes[i];
    }
  }
  return cnt;
}

function solution(c, homes) {
  homes.sort((a, b) => a - b);
  let result = 0;
  let lt = 1;
  let rt = homes[homes.length - 1];
  while (lt <= rt) {
    const mid = Math.floor((lt + rt) / 2);
    if (count(homes, mid) >= c) {
      result = mid;
      lt = mid + 1;
    } else rt = mid - 1;
  }
  return result;
}

console.log(solution(c, homes));

 

---

느낀점

결국 구하고자 하는 것이 무엇인지를 파악하는 것이 중요하다.

가장 인접한 두 공유기 사이의 최대거리를 구해야한다. 따라서 이분탐색의 대상은 두 공유기 사이의 거리이다.

두 공유기 사이의 거리를 계속 탐색하면서 집들에게 거리만큼 공유기를 설치했을 때 몇 개의 집에 설치할 수 있는지를 구한다. 설치해야할 공유기보다 적게 설치했으면 사이의 거리를 좁혀야하고, 설치를 모두 완료했거나 더 설치했다면 거리를 늘려서 최대 거리가 될 때까지 탐색하는 것이다.