[백준] 공유기 설치 2110번 - Java

[백준] 공유기 설치 2110번

나의 풀이

public class RouterInstallation {
    static int[] homes;
    static int C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] values = br.readLine().split(" ");
        int N = Integer.parseInt(values[0]);
        C = Integer.parseInt(values[1]);

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

        Arrays.sort(homes);

        int start = 1;
        int end = homes[N - 1] - start;

        System.out.println(binarySearch(start, end));

    }
    static private int binarySearch(int start, int end) {
        while(start <= end) {
            int count = 1;
            int mid = (start + end) / 2;
            int lastLocate = homes[0];

            for(int home : homes) {
                if(lastLocate + mid <= home) {
                    lastLocate = home;
                    count++;
                }
            }

            if(count >= C) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }
}

• N, C 그리고 집의 좌표들을 입력받고 homes 배열에 넣어준다.
• 이분 탐색을 하기 위해서는 오름차순 정렬은 필수이기 때문에 정렬을 해준다.
• 공유기를 설치할 수 있는 집들간의 간격을 구할 것이다. 그렇기 때문에 start 는 최소 간격인 1, end 는 가장 큰 집의 좌표와 가장 작은 집의 좌표를 간의 거리의 차를 담아준다.
• start 가 end 보다 커질 때까지 반복한다.
• 우선 첫 번째 집의 좌표에 공유기를 설치해두고, 이 집을 기준으로 중간 간격을 더했을 때 이 둘의 합보다 크다면 공유기를 설치할 수 있는 집이된다.
• 때문에 우선 첫 번째 집의 좌표에는 공유기가 설치되어 있기 때문에 count 를 1로 두고, lastLocate(공유기가 설치된 마지막 집의 좌표) 를 homes[0] 으로 둔다.
• 이제 homes 배열을 돌면서 lastLocate + mid 보다 크거나 같다면 count += 1을 해주고, lastLocate 를 해당 집의 좌표로 바꿔준다.
• 만약 count 가 C 보다 크거나 같다면, 이는 간격을 넓혀야 한다는 의미이므로 start = mid + 1을 해준다.
• 아니라면 간격을 좁혀야 하기 때문에 end = mid - 1 을해준다.
• 반복문이 종료되면 최대값이 되는 end 를 리턴해준다.