[Baekjoon] 2110번 : 공유기 설치

1. 문제

https://www.acmicpc.net/problem/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

// 힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면
가장 인접한 두 공유기 사이의 거리는 3이고,
이 거리보다 크게 공유기를 3개 설치할 수 없다.

2. 핵심 아이디어

• 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000
• 이진 탐색을 이용하여 O(N * logX)에 문제를 해결할 수 있음
• 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾음

3. Python 문제풀이

import sys
input = sys.stdin.readline

def bs(arr, start, end) :
  while start <= end :
    mid = (start + end) // 2
    current = arr[0]
    count = 1

    for i in range(1, len(arr)) :
      if arr[i] >= current + mid :
        count += 1
        current = arr[i]

    if count >= c :
      global result
      start = mid + 1
      result = mid
    else :
      end = mid - 1

n, c = list(map(int, input().split(' ')))
arr = []

for _ in range(n) :
  arr.append(int(input()))

arr.sort()

start = 1
end = arr[-1] - arr[0]
result = 0

bs(arr, start, end)
print(result)

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;

class Main {
  public static int[] arr;

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

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    arr = new int[n];

    for (int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }

    Arrays.sort(arr);

    int start = 1;
    int end = arr[n - 1] - arr[0] + 1;

    while (start < end) {
      int mid = (start + end) / 2;

      if (install(mid) < m) {
        end = mid;
      } else {
        start = mid + 1;
      }
    }
    System.out.println(start - 1);
  }

  public static int install(int distance) {
    int count = 1;
    int lastCurrent = arr[0];

    for (int i=0; i<arr.length; i++) {
      int current = arr[i];

      if (current - lastCurrent >= distance) {
        count++;
        lastCurrent = current;
      }
    }
    return count;
  }
}