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

🧩 문제

---

▶ 백준 2110 공유기 설치 바로가기

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

---

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

출력

---

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

예제

---

입력

5 3
1
2
8
4
9

출력

3

🎯 풀이

---

메모리	시간	코드길이
28052 KB	256 ms	1739 B

Point

이분탐색 중 거리를 늘릴지 줄일지를 판단하는 조건이 공유기를 설치하는 개수이다.

1. 이분탐색

while(min < max) {
    int middle = (min + max) / 2;

    //1. 설치할 수 있는 공유기의 개수가 설치해야하는 개수보다 적을 경우
    if(cntInstall(middle) < C) {
        max = middle;   //거리 좁히기
    } else {
        min = middle + 1;   //거리 늘리기
    }

}

이분탐색을 진행한다. 공유기 사이의 거리를 좁히는 기준은 파라미터로 넘겨준 거리를 기준으로 공유기를 설치했을 때 C의 개수보다 적을 경우이다. 설치해야하는 공유기 대수보다 적은 수의 공유기를 설치했기 때문에 거리를 좁히는 것이다.

2. 설치할 수 있는 공유기 개수 세기

private static int cntInstall(int distance) {

    int cnt = 1;
    int lastHouse = houses[0];

    for(int i = 1; i < houses.length; i++) {
        int curHouse = houses[i];

        if(curHouse - lastHouse >= distance) {
            cnt++;
            lastHouse = curHouse;
        }
    }

    return cnt;
}

공유기는 항상 첫번째 집(houses[0])에 설치를 한 후에 마지막으로 공유기를 설치한 집과 현재의 집 사이의 거리가 설정한 거리 이상이라면 현재의 집에 공유기를 설치한다.

⭐️ 전체 풀이 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ2110_공유기설치 {

    private static int[] houses;
    public static void main(String[] args) throws IOException {
        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());   //공유기의 개수

        houses = new int[N];

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

        Arrays.sort(houses);    //이분탐색을 하기 위한 정렬

        int min = 1;    //라우터 최소 거리
        int max = houses[N-1] - houses[0] + 1;  //라우터 최대 거리

        while(min < max) {
            int middle = (min + max) / 2;

            //1. 설치할 수 있는 공유기의 개수가 설치해야하는 개수보다 적을 경우
            if(cntInstall(middle) < C) {
                max = middle;   //거리 좁히기
            } else {
                min = middle + 1;   //거리 늘리기
            }

        }

        System.out.println(max - 1);
    }   //Main 끝

    //공유기를 몇개 설치할 수 있는지 체크
    private static int cntInstall(int distance) {

        int cnt = 1;
        int lastHouse = houses[0];

        for(int i = 1; i < houses.length; i++) {
            int curHouse = houses[i];

            if(curHouse - lastHouse >= distance) {
                cnt++;
                lastHouse = curHouse;
            }
        }

        return cnt;
    }
}