2110 공유기 설치

공유기 설치

문제

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

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

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

입력

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

출력

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

풀이

이 문제는 적절한 집에 c개의 와이파이를 설치하였을 때 와이파이 사이의 가장 인접한 와이파이 사의 거리가 최대인 값을 찾는 문제이다.
즉 집들 중에서 특정 c개의 집을 뽑았을 때 그 사이의 거리가 그 집들중 가장 인접한 집들 사이의 거리가 최대인 경우를 찾는 것이다.
이렇게 설명하면 조금 어렵게 느껴질 수 있는데 알고리즘 문제에서는 입력값에 힌트가 많이 있다.
집의 개수 N과 와이파이의 갯수 c 는 2<= c <= n <= 200,000이다. 이기 때문에 여러 알고리즘을 생각할 수 있다.
그러나 집의 좌표를 나타내는 xi는 범위가 1,000,000,000으로 상당히 크기때문에 log n의 시간복잡도를 가지는 이분탐색을 생각해야 한다.
어차피 정답은 와이파이 사이의 거리이다.
그럼 이 문제에서 정답의 범위는 xi이다.
정답의 범위는 0<= x <= 1,000,000,000이므로 여기서 힌트를 얻고 잘 생각해보자.
이분탐색으로 풀어야 한다는 힌트를 얻고, 입력이 주어졌을 때 정답의 범위를 알기 때문에 이분탐색의 범위는
시작값(start)은 입력들 중 최솟값,
마지막값(end)는 입력들 중 최댓값-최솟값으로 구할 수 있다.
이분탐색의 기본 구조를 따라가며 mid = (start + end) / 2를 구한다.
이 때 mid는 공유기 사이의 거리를 의미한다.
집 들 사이의 거리가 mid이상일 때 공유기를 설치한다고 가정했을 때 설치 되는 공유기의 수를 센다.(cnt)
이 때 cnt가 입력값 c보다 작다면 공유기 사이의 거리(mid)가 큰 것이므로 범위를 줄여 재 탐색한다.
혹은 cnt가 입력값 c보다 크거나 같다면 공유기 사이의 거리(mid)가 작은 것이므로 범위를 늘여 재 탐색한다. (최댓값을 찾아야 하기 때문)

코드

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

public class Main{  

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

        int n = Integer.parseInt(st.nextToken());  
        int c = Integer.parseInt(st.nextToken());  

        int\[\] arr = new int\[n\];  

        for (int i = 0; i < n; i++) {  
            arr\[i\] = Integer.parseInt(br.readLine());  
        }  

        Arrays.sort(arr);  

        int start = 1;  
        int end = arr\[n - 1\] - arr\[0\];  
        int answer = 0;  

        // 이분탐색  
        while(start <= end){  
            int mid = (start + end) / 2;  

            int cnt = 1;  
            int lastWifi = arr\[0\];  

            for (int i = 1; i < n; i++) {  
                if (arr\[i\] >= lastWifi + mid) {  
                    cnt++;  
                    lastWifi = arr\[i\];  
                }  
            }  


            if(cnt >= c){  
                start = mid + 1;  
                // wifi 갯수가 모자란데 mid값이 답이 되면 안되므로 크거나 같을때만 저장  
                answer = mid;  
            }else{  
                end = mid - 1;  
            }  

        }  

        System.out.println(answer);  

    }  
}