[백준] 2110번 공유기 설치

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   직선 상에 중복되지 않은 좌표를 가진 여러 개의 집이 존재하며, 각 집에는 1개의 공유기만 설치가 가능하다. C개의 공유기를 설치할 때 , 가장 인접한 두 공유기 사이의  거리의 최댓값을 구하는 문제이다.

   첫째 줄에는 집의 개수 N, 공유기의 개수 C가 주어지며, 둘째 줄부터는 N개의 줄에 집의 좌표 xi가 한 줄에 하나씩 주어진다. 제한 사항은 다음과 같다.

 

• 2 ≤ N ≤ 200,000
• 2 ≤ C ≤ N
• 0 ≤ xi ≤ 1,000,000,000

 

 

---

접근 방식

   이분 탐색의 개념을 이용해 문제를 해결하였다. 이분 탐색 문제의 경우 대체로 구하고자 하는 대상이 이분 탐색을 수행할 기준이 된다. 이 문제에선 두 공유기 사이의 거리의 최댓값이 구하고자 하는 것이기 때문에 거리를 기준으로 이분 탐색을 진행한다.

   기준이 정해졌으면 이제 범위를 구할 차례이다. 한 집에 두 개의 공유기가 설치될 수는 없기 때문에 거리는 최소 1이며, 첫 번째 집과 마지막 집의 거리가 최대이다. 이제 구해진 거리의 범위를 이분 탐색을 통해 좁혀나가야 한다. 다음 예제를 통해 알아보자.

 

위 : 인덱스 번호, 아래 : 집의 좌표

 

   예제를 기준으로 구한 거리의 범위는 최솟값 1, 최댓값 14이다. 이분 탐색을 위해 중간값을 구해 중간값이 유효한 지 판단할 필요가 있다. 1과 14의 중간값인 7이 공유기 사이의 최대 거리가 될 수 있는지 판단해야 한다.

 

 

   만약 중간값이 유효한 경우 최댓값이 필요하기 때문에 min을 mid + 1로 초기화하고, 유효하지 않은 경우 max를 mid - 1로 초기화하여 탐색하고자 하는 범위를 줄여나간다. 줄어든 범위에서 이전 과정을 반복하며 min이 max보다 커지는 경우 이분 탐색을 종료한다. 이때 max는 구하고자 하는 최댓값이 된다. max값이 왜 구하고자 하는 최댓값이 될까? 가능한 최댓값이 7이라고 가정하고 위의 예제로 과정을 알아보자.

 

 

   다른 경우의 과정은 직접 해보는 것을 권장한다. 위의 설명이 이분 탐색의 결과가 매번 max값이라는 것이 아니라 해당 문제의 경우 이렇게 나온 것임을 착각하지 말자.

 

   거리의 범위를 구하고 이를 이분 탐색하는 과정까지 알아보았다. 이제 이분 탐색으로 구하는 중간값들에 대해 어떻게 배치할 것인가를 구상해야 한다. 그 방법은 간단하다. 이전에 설치한 좌표와 현재 설치할 좌표의 거리차가 현재 탐색 중인 중간값을 만족하는 경우 공유기를 설치하고, 만약 공유기를 다 설치한 경우 해당 중간값이 유효하다고 판단한다. 현재 중간값이 4라고 가정하고 다음 예제를 보자.

 

파란색 : 공유기 설치

 

   공유기 설치가 끝난 경우, 공유기 설치 개수가 요구를 만족했는지 확인해야 한다. 요구를 만족한 경우 해당 중간값은 유효한 값이 된다.

 

※ 최대한 넓은 범위를 사용하기 위해 1번 집에는 공유기는 항상 설치한다.

---

코드

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

public class 백준2110번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(token.nextToken());
        int C = Integer.parseInt(token.nextToken());
        int[] coordinate = new int[N];

        for (int i = 0; i < N; i++)
            coordinate[i] = Integer.parseInt(br.readLine());
        //집의 좌표를 오름차순으로 정렬
        Arrays.sort(coordinate);

        System.out.println(binarySearch(coordinate, coordinate[N - 1] - coordinate[0], C));
    }

    //이분 탐색
    private static int binarySearch(int[] coordinate, int max, int router) {
        int min = 1;

        while (min <= max) {
            //중간값
            int mid = (min + max) / 2;
            //중간값이 유효한 경우 공유기 사이의 거리를 증가하여 다시 진행
            //중간값이 유효하지 않은 경우 공유기 사이의 거리를 감소하여 다시 진행
            if (isValid(coordinate, mid, router)) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        //max를 반환하는 부분이 이해되지 않는 경우 접근 방식 부분을 다시 확인
        return max;
    }

    //거리 유효성 판단
    private static boolean isValid(int[] coordinate, int distance, int router) {
        int pre = 0;
        int next = 1;

        //공유기를 항상 첫번째 집에 설치
        router--;
        //공유기를 전부 배치했거나 next가 배열의 범위를 벗어난 경우 탈출
        while (next < coordinate.length && router != 0) {
            //이분 탐색에서 정한 거리를 만족하는 경우
            //최근 공유기를 설치한 위치를 pre에 저장
            //공유기 수 감소
            if (coordinate[next] - coordinate[pre] >= distance) {
                pre = next;
                router--;
            }
            //공유기 설치 여부에 상관없이 next는 증가
            next++;
        }
        //공유기를 전부 설치한 경우 유효
        if (router == 0) return true;
        //공유기가 남은 경우 해당 거리로는 설치 불가
        return false;
    }
}