[백준] 2110번 : 공유기 설치 (Java)

🔗 2110번 : 공유기 설치
● Java 풀이
● 시간 제한 2초
● 메모리 제한 128 MB

문제

 

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

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

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

 

테스트 케이스

//input
5 3
11
12
18
14
19

//answer
3

// input
2 2
0
1

// answer
1

 

풀이

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

public class Main {
    private static int N, C;
    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());
        N = Integer.parseInt(st.nextToken());
        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 start = houses[0], end = houses[N - 1] + 1, mid;
        while(start < end) {
            mid = (start + end) / 2;  // 최소 거리 이분 탐색
            if(findMinDist(mid - houses[0]) < C) {  // 공유기 개수보다 작게 설치 되었을 때
                //System.out.printf("최소 거리가 %2d일 때, 공유기 설치 불가능...\n", mid - houses[0]);
                end = mid;
            } else {  // 같거나 많을 때
                //System.out.printf("최소 거리가 %2d일 때, 공유기 설치 가능!\n", mid - houses[0]);
                start = mid + 1;  // 거리 조금씩 넓혀가보기 (start = 마지막 공유기 설치 가능 거리)
            }
        }
        System.out.println(start - 1 - houses[0]);
    }

    private static long findMinDist(int dist) {  // 최소 거리 설정
        int count = 1;  // 첫 집 + 1
        int lastRout = houses[0];  // 첫집 선택
        for (int i = 1; i < N; i++) {
            if(dist <= houses[i] - lastRout) {  // 최소거리 이상일 때
                count++;
                lastRout = houses[i];
            }
        }

        //System.out.printf("최소 거리가 %2d일 때, 공유기 설치 가능 개수는 %2d개\n", dist, count);
        return count;
    }
}

 

Upper Bound를 알아야 풀 수 있는 문제였다.

 

Upper Bound란 집합 내 특정 조건을 만족하는 요소의 최대값을 찾는 알고리즘으로,

이분 탐색을 기반으로 작동한다.

범위를 반으로 줄여나가며, 결과적으로 원하는 값의 1 인덱스 초과한 값을 찾아낸다. (left = mid + 1)

public int upperBound(int[] arr, int target) {
	int left = 0;
    int right = arr.length;  // right는 length - 1이 아닌 length로 설정된다
    int mid;
    
    while(left < right) {
    	mid = (left + right) / 2;  // 중간 값
        if(arr[mid] <= target) {  // 중간 값이 목표보다 작거나 같을 시 (목표 충족 시)
        	left = mid + 1;  // 왼쪽 범위 늘리기
        } else {  // 중간 값이 목표보다 클 시 (목표 미충족 시)
        	right = mid;  // 오른쪽 범위 줄이기
        }
    }
    
    return left - 1;  // (결과 값의 1 인덱스 초과한 값) - 1
}

 

여기서 응용해야 할 것은, 그리고 사람들이 많이 틀리는 부분은

1. right 값의 잘못된 초기화. right는 끝 인덱스가 아닌 것을 명심해야 한다.
2. 문제의 응용. 문제는 인덱스로 판별하는 것이 아니라, 집의 거리로 판단하는 것.

위 테스트 케이스가 대표적인 반례로 꼽힐 수 있을 것 같다.

단순히 Upper Bound 알고리즘을 외워 적용하는 것이 아닌, 응용하는 것이 이 문제의 핵심이다.

 

공유기를 서로 멀리 떨어뜨리고, 떨어뜨린 공유기 중 가장 인접한 거리를 구하는 문제이다.

그러므로 문제의 이해 방식은,

가장 인접한 거리를 이분 탐색으로 찾아보고 그만큼, 혹은 그보다 더 떨어진 거리에 공유기를 설치 해본 후 (findMinDist)

공유기 개수가 설치 가능 개수를 넘었을 경우 해당 최소 거리에 공유기를 설치할 수 있다고 보는 것이다. (Upper Bound)

 

나 같은 경우엔 Upper Bound 알고리즘 자체를 처음 접해서,

분하지만... Upper Bound에 대한 이해를 마치고 이를 적용하여 문제를 풀었다.

앞으로 정렬 탐색에서 특정 조건에 최댓값 최솟값을 찾을 때 Upper Bound와 Lower Bound를 떠올릴 수 있는 연습이 필요할 것 같다.