[BOJ] - 공유기 설치/2110번 (JAVA)

[BOJ] - 공유기 설치/2110번 (JAVA)

1. 문제 접근

이분탐색의 개념을 활용하여 구현하는 문제다.

공유기 간 거리에 대해 이분 탐색을 진행하면 된다.

처음 문제에 접근 할 때 공유기 사이의 "최대거리"를 기준으로 이분탐색을 진행하였다.

하지만, 최대거리를 기준으로 이분탐색을 하게 되면, 최대거리를 탐색함과 동시에 가장 인접한 두 공유기 사이의 최대거리를 구하는 것이 번거로웠다.

따라서 최대거리를 기준으로 이분탐색을 하는 것이 아닌, "최소거리"를 기준으로 이분탐색을 진행해야한다.

즉, 배열을 순회하며, 이전 공유기의 위치와의 거리가 설정한 "최소거리"를 만족하면 공유기를 설치하는 것이다.

이분 탐색을 위해 Upper Bound, Lower Bound에 대해 정확하게 설정해야한다.

Upper Bound는 "미만", Lower Bound는 "이상"으로 생각하며 접근한다.

다시 말해 Lower Bound는 포함하며, Upper Bound는 포함하지 않는 것이다.

코드를 통해 살펴보겠다.

int right = array[N - 1] - array[0] + 1;
int left = 1;

초기 Upper Bound와 Lower Bound에 대한 초기화를 하게 된다.

"Lower Bound 이상, Upper Bound 미만"이므로, 공유기간 최소 거리가 될 수 있는 최소값은 1, 최대값은 마지막 집과 처음 집의 위치 차이에 1을 더한 값이다.

while (left <= right) {...}

이분 탐색의 종료 조건은 상한과 하한이 역전되는 것이다.

int mid = (right + left) / 2; // 공유기 간 최소 거리
int routerCnt = 1;
int prevRouterPos = array[0];

mid변수가 공유기간의 설치 할 수 있는 최소 거리다.

routerCnt는 해당 최소거리로 공유기를 설치하였을 때, 설치되는 총 공유기의 개수다.

prevRouterPos는 가장 마지막으로 공유기를 설치한 위치를 저장하는 변수다.

for (int i = 1; i < N; ++i) {
    if (array[i] - prevRouterPos >= mid) {
        // i의 위치에 공유기 설치
        prevRouterPos = array[i];
        ++routerCnt;
    }
}

모든 집의 위치를 순회하며 해당 집의 위치가 이전 공유기의 위치와 조회 중인 집의 위치간의 거리 차이가 공유기를 설치할 수 있는 최소거리 "이상"인 경우, 해당 집에 공유기를 설치하며, 이전 공유기의 위치에 대한 변수(prevRouterPos)를 갱신하고, 공유기의 수(routerCnt)를 증가시킨다.

if (routerCnt < C) {
    // 최소거리가 너무 크다
    // 공유기가 너무 적게 설치
    right = mid - 1;
    continue;
}        

모든 집에 대해 순회가 끝나고 설치한 공유기의 수가 주어진 공유기의 수 보다 적을 경우, 최소거리가 너무 크게 설정되어 공유기가 적게 설치된 것이다.

따라서 최소거리를 작게 조정할 필요가 있으므로 최소거리의 "상한 값"을 작게 수정한다.

else {
    // 최소거리가 너무 작다
    // 너무 많은 공유기가 설치
    left = mid + 1;
}

반대로, 설치한 공유기의 수가 주어진 공유기의 수 보다 같거나 많을 경우, 최소거리의 "하한 값"을 크게 수정해야한다.

2가지 경우가 있는데, 공유기 수가 같거나, 많을 경우가 있다.

1. 설치된 공유기의 수가 많을 경우
   • 정답이 될 수 없으며, 정답을 찾기 위해 최소거리를 크게 설정하여야 한다.
2. 설치된 공유기의 수가 주어진 공유기의 수와 동일할 경우
   • 해당 최소거리가 정답이 될 수 있다.
   • 하지만, 문제의 해는 "인접한 두 공유기 사이의 최대 거리"이다.
   • 따라서 최소거리를 크게 설정하여 계속 확인 할 필요가 있다.

 ans = Math.max(ans, mid);

해당 최소거리를 통해 모든 과정을 완료하면, 이전의 최소거리와 비교하여 더 큰 값으로 갱신한다.

이분 탐색이 종료되면, 최종적으로 "인접한 두 공유기 사이의 최대 거리"를 구할 수 있다.

2. 코드

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

public class Main {
    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[] array = new int[N];
        for (int i = 0; i < N; ++i) {
            array[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(array);

        // 두 공유기 사이 거리의 최대(right), 최소값(left)
        int right = array[N - 1] - array[0] + 1;
        int left = 1;
        int ans = left;

        while (left <= right) {
            int routerCnt = 1;
            int prevRouterPos = array[0];
            int mid = (right + left) / 2; // 공유기 간 최소 거리

            for (int i = 1; i < N; ++i) {
                if (array[i] - prevRouterPos >= mid) {
                    // i의 위치에 공유기 설치
                    prevRouterPos = array[i];
                    ++routerCnt;
                }
            }
            if (routerCnt < C) {
                // 최소거리가 너무 크다
                // 공유기가 너무 적게 설치
                right = mid - 1;
                continue;
            } else {
                // 최소거리가 너무 작다
                // 너무 많은 공유기가 설치
                left = mid + 1;
            }
            ans = Math.max(ans, mid);
        }
        System.out.println(ans);
    }
}