[JAVA11/알고리즘] BOJ 2110 : 공유기 설치

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 💬 문제

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

 

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

 

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

🔨 입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

🔨출력 

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

👊🏻 예시 입력 1 

5 3
1
2
8
4
9

👊🏻 예시 출력 1

 

3

 

 

💡 해결

이 문제를 이분탐색을 이용하여서 풀었다.

함수들 먼저 설명하겠다.

 

public static int count(int[] arr, int dist){
        int cnt = 1;
        int ep = arr[0];
        for(int i= 1; i<arr.length; i++){
            if(arr[i] - ep>=dist){
                cnt++;
                ep = arr[i];
            }
        }
        return cnt;
    }

먼저, count 함수이다.

 

배열과 거리를 넣어주었을때, 그 사이 거리 이상의 거리에 위치한 집들의 개수를 센다.

그리고 그 개수를 리턴해주는 함수이다.

 

 

public static int solution(int n, int c, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        int lt = 1;
        int rt = arr[n-1];
        while(lt<=rt){
            int mid = (lt+rt)/2;
            if(count(arr,mid)>=c){
                answer = mid;
                lt = mid+1;
            }
            else rt = mid-1;
        }
        return answer;
    }

 

그리고, 그 count 함수를 사용해서 만든 solution 함수이다.

여기선, 이분탐색을 이용하여 가장 인접한 공유기 사이의 거리의 최댓값을 구해줄 것이다. 

먼저, 이분탐색을 하기전에 배열을 정렬해주어야 한다.

 

lt를 1로, rt는 배열의 마지막값으로 잡아준다. mid값을 둘 사이의 가운데 값으로 지정해준다.

count(arr,mid)값이

입력받은 공유기의 개수보다 많을땐 모두 가능하므로 그 mid 값을 답으로 넣어주고, lt를 mid +1로 바꿔주고 계속해서 진행한다.

만약, 적다면 문제에서 요구하는바에 맞지 않으므로 rt를 mid-1로 바꿔서 진행해준다.

 

👨🏻‍💻  CODE
 

import java.util.*;

public class Main {
    public static int count(int[] arr, int dist){
        int cnt = 1;
        int ep = arr[0];
        for(int i= 1; i<arr.length; i++){
            if(arr[i] - ep>=dist){
                cnt++;
                ep = arr[i];
            }
        }
        return cnt;
    }
    public static int solution(int n, int c, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        int lt = 1;
        int rt = arr[n-1];
        while(lt<=rt){
            int mid = (lt+rt)/2;
            if(count(arr,mid)>=c){
                answer = mid;
                lt = mid+1;
            }
            else rt = mid-1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int c = in.nextInt();
        int[] arr= new int[n];
        for(int i=0; i<n; i++){
            arr[i] = in.nextInt();
        }
        System.out.println(solution(n,c,arr));
    }
}

 

 

💪🏻 결과

어렵다.. 코드로 구현하는것은 그렇게 어렵지 않았는데, 푸는 방법을 구상하는것이 어려웠다..
자주 나오는 알고리즘이기 때문에 공부를 많이 해둬야겠다.