[Algorithm] 백준 이분탐색 문제 - 공유기 설치(2110) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 이분탐색 문제 - 공유기 설치 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int[] house;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());

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

        int left = 1; // 최소 거리는 1
        int right = house[n - 1] - house[0] + 1; // 최대 거리는 양끝 값 차이 + 1

        while (left < right) { // upper bound로 찾기
            int mid = left + (right - left) / 2; // 두 거리의 중점으로 거리 업데이트

            int count = installWifi(mid);
            if (count < m) right = mid; // 설치된 개수가 m에 만족하지 않는 경우 더 설치 해야하므로 최소 거리 줄이기
            else left = mid + 1; // 최소 거리를 만족하므로 더 길게 가능한지 파악하기 위해 left 업데이트
        }

        System.out.println(left - 1);
    }

    static int installWifi(int distance) {
        int lastLoc = house[0]; // lastLoc은 맨 처음집으로 설정
        int count = 1; // lastLoc은 1번 집 설정하므로 개수 1

        for (int i = 0; i < n; i++) {
            int nowLoc = house[i];

            if (nowLoc - lastLoc >= distance) { // 최소 거리보다 크다면
                count++; // 개수 증가
                lastLoc = nowLoc; // 마지막 위치 업데이트
            }
        }
        return count;
    }
}

 

2. 풀이 중점 사항

 

해당 문제는 이분탐색을 어느 것으로 설정하느냐가 중요한 포인트였습니다.

m개의 공유기를 설치해야 하므로, 공유기 위치를 콤비네이션으로 정의하게 된다면 그 경우의 수가 10억 C 20만 까지 될 수 있으므로 시간초과가 발생할 수 있습니다.

 

따라서, 최단 거리를 이분탐색하여, m개의 공유기를 만족하는 가장 큰 값을 찾는 방법으로 문제를 정의할 수 있습니다.

 

예를 들어 이분탐색한 결과 집 간 인접한 두 공유기의 사이의 최대 거리가 3일 때, 10개의 공유기를 설치할 수 있습니다.

이는 곳 1, 4, 10, 15 .... 혹은 1, 4, 7, 14...로 10개를 설치했음을 의미합니다.

 

m개의 공유기를 만족하기 때문에 mid 값인 3에 +1을 하여 길이를 4로 만들고 다시 탐색하여 공유기 10개를 설치할 수 있는지 판단합니다. 만약 m개를 만족하지 않는다면 right = 4를 설정하여 다시 이분탐색을 진행하는 것입니다.

 

이 원리를 적용하면,

집의 개수 최대 20만,

공유기 개수 최대 20만

이분 탐색 0 ~ 10억 사이의 거리이므로 log10억  = 약 28 ~ 30 사이쯤

 

이분탐색하는 횟수 * 집을 탐색하며 공유기를 설치하는 횟수 

= O(20만 * 30) = O(600만) 정도로 생각할 수 있습니다.

 

3. 코드로 확인하기

 

int left = 1; // 최소 거리는 1
int right = house[n - 1] - house[0] + 1; // 최대 거리는 양끝 값 차이 + 1

 

따라서, 길이의 최소 거리를 의미하는 1과 각 집의 가장 양끝에 있는 거리를 left, right로 설정하여, mid를 구합니다.

mid를 최단 거리로 설정하여, 마지막 설치된 공유기의 길이에서 지금 설치하는 공유기 길이가 최소거리보다 큰 경우에만 업데이트합니다. (만약 최소 거리보다 작다면 카운트 개수가 증가하지 않으므로, m 개수를 만족하지 않는다면 이분탐색을 다시 실행)

 

static int installWifi(int distance) {
    int lastLoc = house[0]; // lastLoc은 맨 처음집으로 설정
    int count = 1; // lastLoc은 1번 집 설정하므로 개수 1

    for (int i = 0; i < n; i++) {
        int nowLoc = house[i];

        if (nowLoc - lastLoc >= distance) { // 최소 거리보다 크다면
            count++; // 개수 증가
            lastLoc = nowLoc; // 마지막 위치 업데이트
        }
    }
    return count;
}

 

while (left < right) { // upper bound로 찾기
    int mid = left + (right - left) / 2; // 두 거리의 중점으로 거리 업데이트

    int count = installWifi(mid);
    if (count < m) right = mid; // 설치된 개수가 m에 만족하지 않는 경우 더 설치 해야하므로 최소 거리 줄이기
    else left = mid + 1; // 최소 거리를 만족하므로 더 길게 가능한지 파악하기 위해 left 업데이트
}

이렇게 얻은 count로 m개에 만족, 불만족하는지 판단한후 upper bound 형식으로 이분탐색을 진행합니다.

이상으로 백준 공유기 설치 자바 풀이를 마치도록 하겠습니다. 감사합니다.! 

 

참고 블로그: https://st-lab.tistory.com/277