프로그래머스 : 징검다리

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        int front = 1;
        int rear = distance;
        while(front<=rear){
            int mid = (front + rear)/2;
            int prev=0;
            int cnt = 0;
            for(int rock : rocks){
                if(rock - prev < mid){
                    cnt++;
                }else{
                    prev = rock;
                }
            }
            if(distance - prev < mid)
                cnt++;

            if(cnt > n){
                rear = mid-1;
            }else{
                // cnt <=n 이 후보인 이유는 최소값 mid에 대해서 n보다 작기만 하다면 후보로 속한다.
                // 가량 정답이 15인 녀석이 있는데
                // 15라는 녀석은 cnt가 8 9 일 때 만들 수 있다고 치자 근데 만약 제한값이 9 라고한다면
                // n == cnt 일때만 검사를 한다면 15텀에서 비교햇엇는데 못하고 16~30 에서 조사하기때문에 15에서 찾아야하는 분기점을 놓침
                // 따라서 mid 값을 만들 수 있을 때 n <= cnt라면 후보임 당연히 적을 때도 이값을 구할 수 있으니 후보고 실제로 이값에서 더 커지거나 같아지거나 하는 선택지 빡에없음.
                answer = Math.max(answer,mid);
                front = mid+1;
            }
            
        }
        
        return answer;
    }
}