[BOJ] 2110번 : 공유기 설치

코드

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

public class Main {
	
	static int n, c;
	static int[] homePosition;
	
	public static void main (String[] args) {
		input();
		System.out.println(func());
	}
	
	static void input() {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		c = sc.nextInt();
		homePosition = new int[n];
		
		for (int i = 0; i < n; ++i) {
			homePosition[i] = sc.nextInt();
		}

		sc.close();
	}
	
	static int func() {
		// 집의 위치를 정렬하여 집 사이의 거리를 구한다.
		Arrays.sort(homePosition);
		
		int left = 0;
		int right = 1_000_000_000;
		int result = -1;
		
		// 이진 검색으로 답을 구한다.
		while (right >= left) {
			int mid = (left + right) / 2;
			
			// 최단 거리가 mid일 때, 가진 공유기 수 이상으로 공유기를
			// 설치 가능하면 더 긴 최단거리에서 가진 공유기 수 이상으로
			// 설치 가능한지 살펴봐야한다.
			if (getInstallCount(mid) >= c) {
				result = mid;
				left = mid + 1;
			} else {
				// 최단 거리가 mid일 때, 가진 공유기 수 보다 적게 설치 
				// 가능할 경우 최단 거리가 더 짧은 경우를 살펴봐야한다.
				right = mid - 1;
			}
		}

		return result;
	}
	
	// 최단 거리가 minDistance일 때, 공유기를 몇개 설치할 수 있는지 반환
	static int getInstallCount(int minDistance) {
		int count = 1;
		int lastPosition = homePosition[0];
		
		for (int i = 1; i < homePosition.length; ++i) {
			if (homePosition[i] - lastPosition >= minDistance) {
				lastPosition = homePosition[i];
				++count;
			}
		}
		
		return count;
	}
}