BinarySearch 백준 알고리즘 자바 2110 ‘공유기 설치’ 문제풀이

Problem

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

Input 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

Output 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

Solution

무엇을 이분 탐색할 것인가가 관건인 것 같다. 무조건 첫번째 집에는 설치한다는 가정하에 진행했다. (가장 먼 거리를 뽑아야 하므로..?)

• 주어지는 집의 최소 개수는 2이고, 최소 공유기의 수도 2이므로 이분 탐색에서 left 값은 1로 시작한다.
• right 값은 첫번째 집과 가장 멀리 있는 집과의 거리로 시작한다.
• 일반적인 이분 탐색과 비슷하나, 공유기를 설치한 집의 개수가 입력 받은 C와 대소비교를 해야하며 방금 설치한 집과 지금 집과의 거리를 비교해야 한다.
• 공유기 설치가 목표보다 많이 했으면 설치 거리를 늘려주고 아니면 줄여준다.

Code

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), c = scan.nextInt();
		
		int[] houses = new int[n];
		for(int i = 0; i < n; i++) houses[i] = scan.nextInt();
		Arrays.sort(houses);
		
		int left = 1, right = houses[n-1] - houses[0], mid = 0;
		while(left <= right) {
			int cnt = 1, prev = houses[0];
			mid = (left + right) / 2;
			
			for(int house : houses) {
				if(house - prev >= mid) {
					cnt++; prev = house;
				}
			}
			
			if(cnt >= c) left = mid + 1;
			else right = mid - 1;
		}
		System.out.print(right);
	}
}