[BOJ/BinarySearch] 백준 2110 - 공유기 설치 (Java)

2110 - 공유기 설치

https://www.acmicpc.net/problem/2110

문제

도현이의 집 N개가 수직선 위에 있고 각각의 집의 좌표는 $X_1$, ..., $X_N$
집 여러 개가 같은 좌표를 가지는 일 X
언제 어디서나 와이파이 즐기기 위해 공유기 C개 설치하려고 함/ 최대한 많은 곳에서 와이파이 사용하려고 함
-> 한 집에는 공유기 하나만 설치 O, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 함

=> C개의 공유기 N개의 집에 적당히 설치 -> 가장 인접한 두 공유기 사이의 거리 최대

입력
첫째 줄: 집의 개수 N (2 <= N <= 200,000), 공유기 개수 C (2 <= C <= N)
둘째 줄부터 N개의 줄: 집의 좌표 $x_i$ (0 <= $x_i$ <= 1,000,000,000)
출력: 가장 인접한 두 공유기 사이의 최대 거리

---

풀이

이진 탐색(Binary Search)

• 정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘
• 시간복잡도: O(log N)

 

• 가장 가까운 두 공유기 사이의 최소 거리를 최대
• 거리 d 조정 -> 설치 여부 확인
  • 설치 O -> 거리 넓힘 `lt = mid + 1`
  • 설치 X -> 거리 좁힘 `rt = mid - 1`

int lt = 1;
int rt = x[N - 1] - x[0];
int result = 0;

while (lt <= rt) {
    int cnt = 1; 
    int cur = x[0];
    int mid = (lt + rt) / 2;

    for (int i = 1; i < N; i++) {
        if (x[i] - cur >= mid) {
            cnt++;
            cur = x[i];
        }
    }

    if (cnt >= C) {
        result = mid;
        lt = mid + 1;
    } else rt = mid - 1;
}

---

예시

N = 5, C = 3, x = [1, 2, 8, 4, 9] 

-> 오름차순 정렬: x = [1, 2, 4, 8, 9]

 

• lt = 1, rt = 9 - 1 = 8, result = 0
  • cnt = 1, cur = 1, mid = (1 + 8) / 2 = 4
    • i = 1 -> x[1](2) - 1 = 1 -> 1 < 4 (X)
    • i = 2 -> x[2](4) - 1 = 3 -> 3 < 4 (X)
    • i = 3 -> x[3](8) - 1 = 7 -> 7 >= 4 (O)
      => cnt = 2, cur = 8
    • i = 4 -> x[4](9) - 1 = 1 -> 1 < 4 (X)
• cnt(2) < 3 -> rt = mid - 1 = 3 
  • cnt = 1, cur = 1, mid = (1 + 3) / 2 = 2
    • i = 1 -> x[1](2) - 1 = 1 -> 1 < 2 (X)
    • i = 2 -> x[2](4) - 1 = 3 -> 3 > 2 (O)
      => cnt = 2, cur = 4
    • i = 3 -> x[3](8) - 4 = 4 -> 4 > 2 (O)
      => cnt = 3, cur = 8
    • i = 4 -> x[4](9) - 8 = 1 -> 1 < 2 (X)
• cnt(3) >= 3 -> result = 2, lt = mid + 1 = 3
  • cnt = 1, cur = 1, mid = (3 + 3) / 2 = 3
    • i = 1 -> x[1](2) - 1 = 1 -> 1 < 3 (X)
    • i = 2 -> x[2](4) - 1 = 3 -> 3 >= 3 (O)
      => cnt = 2, cur = 4
    • i = 3 -> x[3](8) - 4 = 4 -> 4 > 3 (O)
      => cnt = 3, cur = 8
    • i = 4 -> x[4](9) - 8 = 1 -> 1 < 2 (X)
• cnt(3) >= 3 -> result = 3, lt = mid + 1 = 4

=> lt = 4, rt = 3 -> X

---

코드

import java.io.*;
import java.util.*;

// 공유기 설치
public class boj_2110 {
    static int N, C;
    static int[] x;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        x = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(x);

        int lt = 1;
        int rt = x[N - 1] - x[0];
        int result = 0;

        while (lt <= rt) {
            int cnt = 1;
            int cur = x[0];
            int mid = (lt + rt) / 2;

            for (int i = 1; i < N; i++) {
                if (x[i] - cur >= mid) {
                    cnt++;
                    cur = x[i];
                }
            }

            if (cnt >= C) {
                result = mid;
                lt = mid + 1;
            } else rt = mid - 1;
        }

        System.out.println(result);
    }
}