[백준, 자바, 2110번] 공유기 설치(이분 탐색)

풀이

• 뭔가 문제를 제대로 이해하지 못했어서 시간이 좀 더 걸린 문제로
• 문제 해결 방법은 정말 단순하게 이분 탐색 문제인데
• 왠지 모르게 지난 풀이 방법으론 해결 방법에 대한 뎁스가 한 개 더 있는 듯한 느낌이었어서
• 더 꼬이게 되어버림...
• 그리고 이분 탐색의 결과 도출에 대한 것으로 하나 상기된 것은
• 결과가 나왔을 경우 계속해서 탐색할 때
• 같을 경우와 부족할 경우를 함께 묶어 처리를 하는 것을 다시 상기하게 되었음.

 

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

public class _2110 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] li = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = li[0];
        int c = li[1];

        // 집 위치 체크
        int[] check = new int[n];
        for (int i=0; i<n; i++) check[i] = Integer.parseInt(br.readLine());
        Arrays.sort(check);

        // 이분 탐색 시작
        System.out.println(B_Search(check, c));

    }

    public static int B_Search(int[] check, int c) {
        // 이분 탐색 시작
        int s = 0;
        int e = check[check.length-1]-check[0];

        int mx_range = 0;

        while (s<=e) {
            int m = (s+e)/2;
            int cnt = 1;
            int now = check[0];

            for (int i=1; i<check.length; i++) {
                if (check[i]-now >= m) {
                    cnt++;
                    now = check[i];
                }
            }

            if (cnt >= c) {
                mx_range = Math.max(mx_range, m);
                s = m+1;
            }
            else e = m-1;
        }
        return mx_range;
    }
}