[240318] 알고리즘 리부트 32일차 - 백준 2110 자바

[Part1-Chapter07-Clip10]

- 백준 2110 공유기 설치

정말 어리석게도 이분탐색으로 공유기를 설치할 집을 찾고 있었다. 사실 이런 접근을 생각하지 못하고 있었다. 그래도 정리해보자면 우리가 구하고자 하는 값은 인접한 공유기가 가질 수 있는 최대 거리! 이 값을 이분 탐색으로 처리한다. left가 되는 가장 작은 값은 한 집에 한 공유기를 설치할 수 있고 연속된 두 집에 모두 공유기가 설치되어 있다면 그 경우 1이 된다. right 값, 즉 인접한 공유기 거리가 최대가 되는 경우는 집 배열을 오름차순으로 정렬했을 때 가장 첫 번째 원소와 가장 마지막 원소의 집에 공유기를 설치하는 경우다. 

이렇게 이분 탐색을 진행하는데 임시 공유기 거리인 중간 값을 기준으로 공유기를 설치한다 가정하고 이를 위해 집 배열에 대해 반복문을 수행한다. 첫번째 집은 무조건 공유기를 설치해야 최대 거리를 만드는 데 유리하기 때문에 이전 집을 첫번째 원소로 설정한다 그리고 반복문을 돌면서 그 다음 집의 위치와 이전 집의 위치로 거리를 계산했을 때 중간 값 즉, 임시 공유기 거리보다 크거나 같으면 설치 대수를 증가 시키고 이전 집을 다시 해당 원소로 설정한다. 

이렇게 구한 공유기의 설치 대수를 목표 대수와 비교해서 더 많이 설치될 수 있거나 같은 경우 l을 늘리고 답을 갱신한다. 반대로 목표대수보다 적다면 r을 줄여서 거리를 좁혀 이분탐색을 다시 진행한다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();

        int[] houses = new int[n];

        for (int i = 0; i < n; i++) {
            houses[i] = sc.nextInt();
        }

        Arrays.sort(houses);
        //System.out.println(Arrays.toString(houses));

        int l = 1;
        int r = houses[n - 1] - houses[0];
        int ans = -1;
        // 구하고자 하는 공유기 간의 거리를 이분 탐색의 대상으로 잡고!

        while (l <= r) {
            int m = (l + r) / 2;

            if (installedNum(m, houses) >= c) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        System.out.println(ans);
    }

    private static int installedNum(int m, int[] houses) {
        int cnt = 1;

        int before = houses[0];

        for (int i = 1; i < houses.length; i++) {
            if (houses[i] - before >= m) {
                cnt++;
                before = houses[i];
            }
        }
        return cnt;
    }
}