[백준/이분탐색] 2110번 공유기 설치 (JAVA)

문제

---

풀이

주어진 값의 범위가 커서 DFS가 아닌 이분 탐색으로 접근해야 하는 문제였다.

중요한 로직은 다음과 같다.

1. targetDistance를 기준으로 이분탐색을 진행하며
2. 이 targetDistance를 만들기 위해 몇 개의 공유기를 설치해야 하는지 계산하고
3. 필요한 공유기가 c와 동일한지 확인하다.

로직을 코드로 표현하기 위해 크게 2가지 메서드를 활용했다.

1. calcMaxDistance(left, right)
   • 이분 탐색을 진행하는 메서드이다.
   • mid를 가장 인접한 공유기 거리로 설정하고, 설치한 공유기 개수와 비교한다.
   • 이분 탐색이 끝나면 최대 인접 공유기 거리를 반환한다.

2. countRouters(targetDistance)
   • targetDistance를 만족시키기 위해 필요한 최소의 공유기 개수를 세는 메서드이다.
   • 공유기 거리를 탐색하며 거리가 targetDistance 이상인 경우 공유기를 추가로 설치한다.
   • 첫 번째 공유기를 필수로 포함하는 이유는, 오름차순으로 정렬되어 있어서 공유기 거리를 최대로 보장하기 때문이다.

이 때 이분 탐색은 재귀와 반복문으로 모두 구현이 가능하다. 두 가지 방법으로 아래 코드를 적었다.

반복문 코드

import java.io.*;
import java.util.Arrays;

public class Main {

    private static final int MIN_DIST = 1;

    private static int n;
    private static int c;
    private static int[] houses;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        parseInput(br);
        bw.append(String.valueOf(calcMaxDistance(MIN_DIST, distance(0, n - 1))));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        c = Integer.parseInt(line[1]);

        houses = new int[n];
        for (int i = 0; i < n; i++)
            houses[i] = Integer.parseInt(br.readLine());
        Arrays.sort(houses);
    }

    private static int distance(int left, int right) {
        return houses[right] - houses[left];
    }

    private static int calcMaxDistance(int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (countRouters(mid) >= c) left = mid + 1;
            else right = mid - 1;
        }
        return (left + right) / 2;
    }

    private static int countRouters(int targetDistance) {
        int count = 1, prev = 0;
        for (int i = 1; i < n; i++) {
            if (distance(prev, i) >= targetDistance) {
                count++;
                prev = i;
            }
        }
        return count;
    }
}

재귀 코드

import java.io.*;
import java.util.Arrays;

public class Main {

    private static final int MIN_DIST = 1;

    private static int n;
    private static int c;
    private static int[] houses;

    private static int maxDistance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        parseInput(br);
        calcMaxDistance(MIN_DIST, distance(0, n - 1));
        bw.append(String.valueOf(maxDistance));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        c = Integer.parseInt(line[1]);

        houses = new int[n];
        for (int i = 0; i < n; i++)
            houses[i] = Integer.parseInt(br.readLine());
        Arrays.sort(houses);
    }

    private static int distance(int left, int right) {
        return houses[right] - houses[left];
    }

    private static void calcMaxDistance(int left, int right) {
        int mid = (left + right) / 2;

        if (left > right) {
            maxDistance = mid;
            return;
        }
        
        if (countRouters(mid) < c) calcMaxDistance(left, mid - 1);
        else calcMaxDistance(mid + 1, right);
    }

    private static int countRouters(int targetDistance) {
        int count = 1, prev = 0;
        for (int i = 1; i < n; i++) {
            if (distance(prev, i) >= targetDistance) {
                count++;
                prev = i;
            }
        }
        return count;
    }
}