[백준] BOJ - 2110 공유기 설치 자바 JAVA (골드 4)

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

2110번: 공유기 설치

 

 

나의풀이

import java.util.*;
import java.io.*;
public class Main {
    static int[] house;
    public static int isPossible(int distance){//최소거리가 주어짐 
        int count=1;
        int prev=house[0];//직전에 설치한 집 
        for(int i=1; i<house.length;i++){
            int temp = house[i];
            
            if(temp-prev>= distance){//직전 설치 집과 거리가 최소거리 이상인가 (그래야만 설치가능)
                count++;
                prev=temp;//지금 집을 이전 집으로 바꿔주기
            }
        }
        return count;//설치 가능한 공유기 개수임 
    }
    
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken()); //집의개수 
        int c = Integer.parseInt(st.nextToken()); //공유기 개수
        
        house= new int[n];
        for(int i=0; i<n; i++){
            house[i]=Integer.parseInt(br.readLine());
        }
        
        //이분탐색을 위해 정렬(필수)
        Arrays.sort(house);
        
        int left=1;//최소거리로 가능한 최솟값
        int right=house[n-1]-house[0]; //최소거리고 가능한 최댓값 
        int mid=0;
        
        while(left<=right){
            mid=(left+right)/2;    
            int possibleCnt=isPossible(mid); //mid가 최소거리일때 설치 가능한 공유기 개수 
            if(possibleCnt< c){//공유기를 더 설치할 수 있게 최소거리를 줄여줘야함 
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        
        bw.write(Integer.toString(right));
        bw.flush();
        br.close();
        bw.close();
    }
}