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. 배열 정렬

정렬 전 : 1, 2, 8, 4, 9
정렬 후 : 1, 2, 4, 8, 9

2. 이분 탐색

int ans = 1;
int start = 1;
int end = a[a.length-1]-a[0]; //가능한 최대 거리
while (start <= end) {
	int mid = (start+end)/2;
	if (check(a, mid, target)) {
		ans = Math.max(ans,mid);
		start = mid+1;
	} else {
	    end = mid-1;
	}
    }

처음에 end = 8이고,
mid = 4 가 된다.
이 때 check 함수에서는
거리가 4일때 공유기가 몇개사 설치되는지 확인해야한다.
좌표 1에서 거리 4를 더하면 5이지만 배열에서는 5에 집이 없다. 그러므로 8에 설치해야한다. 그리고 8에서 거리가 5이면 12인데 그럼 배열 값을 벗어난다.
공유기는 결국 2개만 설치했기때문에 false가 return 된다.

end = 3, mid = 2가되고 아까를 반복한다.
거리가 2이라면 공유기는3개 설치가 가능하다.
하지만 3개를 설치할수있는 최대 거리를 찾아야하기때문에 계속 반복한다.

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

public class Main {
	public static long binarySearch(int[] a, int target) {
		  int ans = 1;
	        int start = 1;
	        int end = a[a.length-1]-a[0]; //가능한 최대 거리

	        while (start <= end) {
	            int mid = (start+end)/2;
	            if (check(a, mid, target)) {
	                ans = Math.max(ans,mid);
	                start = mid+1;
	            } else {
	                end = mid-1;
	            }
	        }
			return ans;
	}
	public static boolean check(int[] a, int dist, int c) {
		int cnt = 1;
        int last = a[0]+dist; //첫 번째 값 + 거리
        for(int i=0; i<a.length; i++) {
            if(a[i] >= last) {
                cnt++;
                last = a[i]+dist; //마지막 값 + 거리
            }
        }
        return cnt >= c;
	}
	public static void main(String[] agrs) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		int N = Integer.parseInt(tokenizer.nextToken());
		int M = Integer.parseInt(tokenizer.nextToken());
		// tokenizer = new StringTokenizer(reader.readLine());
		int ans = 0;
		int[] arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(reader.readLine());
		Arrays.sort(arr);
		long max = arr[N - 1];
		System.out.print(binarySearch(arr, M));
	}
}