[알고리즘]Searching - 마구간 정하기(결정 알고리즘)

10. 마구간 정하기(결정알고리즘)
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램

입력) 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
출력) 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

 

import java.util.Arrays;
import java.util.Scanner;

public class Main { // binary search
	
	public static int count(int[] arr, int dist) { // 최대 거리에 해당하는 말의 수
		int cnt = 1, pos = arr[0]; // cnt : 배치한 말의 수 // pos : 마구간에 놓인 말
		
		for (int i=1; i<arr.length; i++) {
			if (arr[i]-pos>=dist) {
				cnt++;
				pos = arr[i];
			}
		}
		return cnt;
	}
	
	public static int solution(int n, int c, int[] arr) {
		int answer = 0;		
		Arrays.sort(arr); // 오름차순 정렬
		
		int lt = 1, rt = arr[n-1]; // lt : 최소 거리(1) // rt : 배열의 가장 끝 숫자 
		while (lt<=rt) {
			int mid = (lt+rt)/2; // 최대 거리
			if (count(arr, mid)>=c) {
				answer = mid;
				lt = mid+1;
			} else {
				rt = mid-1; // 최대 거리 범위 줄임
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // 마구간 수
		int c = scanner.nextInt(); // 말 마릿수
		int[] arr = new int[n];
		for (int i=0; i<n; i++) { // 마구간 좌표
			arr[i] = scanner.nextInt();
		}
		System.out.println(solution(n,c,arr));
	}

}

---

결과

입력
5 3
1 2 8 4 9

출력
3