문제 - 공유기 설치

문제접근

가장 인접한 두 공유기 사이의 거리를 구하기 위해서 이분탐색을 이용했다.
1. 해당 집의 좌표를 오름차순으로 정렬
2. 집의 좌표는 (0 ≤ xi ≤ 1,000,000,000)이므로 최솟값은 0, 최대값은 1,000,000,000으로 설정을 해준다.
3. 거리(mid)만큼 공유기를 설치하여 총 몇개의 집에 설치할 수 있는지 확인
4. C보다 작은 경우에는 최소 거리를 줄여주기 위해서 mid-1
5. c보다 크거나 같은 경우에는 최소 거리를 크게하기 위해서 mid+1

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int ans;
    public static void main(String[] args) throws  Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int ans = 0;
        int house[] = new int[N];

        for(int i=0;i<N;i++)
        {
            st = new StringTokenizer(br.readLine());
            house[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(house);

        //이분탐색
        int left = 0;
        int right = 1_000_000_000;

        while(left <= right)
        {
            int mid = (left+right)/2;
            //공유기 설치하는 집의 갯수
            int count =1;
            int first = house[0];

            for(int i=1;i<N;i++)
            {
                //공유기의 오른쪽 전파위치의 집추출
                if(first + mid <= house[i])
                {
                    first = house[i];
                    count++;
                }
            }

            if(count < C) {
                right = mid - 1;
            }
            else {
                left = mid +1;
                ans = mid;
            }
        }
        System.out.println(ans);
    }
}