[프로그래머스] 징검다리

풀이

최솟값을 이분탐색으로 찾아낸다. 범위는 0 ~ distance이다. 돌과 돌사이의 거리를 구하고 현재의 최솟값과 비교하여 없애야 하는 돌의 개수를 구한다. 현재의 최솟값을 만족 시키기위한 돌의 개수와 매개 변수로 주어진 제거해야할 돌의 개수n과 다시 비교한다. n과 같거나 이하인 경우, n보다 큰 경우를 분기처리하여 최솟값을 조절해서 값을 구해낸다.

코드

import java.util.*;

class Solution {
      public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        return binerySearch(distance, rocks, n);
    }
    
    public int binerySearch(int d, int[] r, int n){
        int left = 0;
        int right = d;
        int mid = (left+right)/2;
        int ans = 0;
        while (left <= right){
            int prev = 0;
            int count = 0;
            mid = (left+right)/2;
            for (int i=0; i<r.length; i++){
                if (r[i]-prev < mid)
                    count++;
                else{
                    prev = r[i];
                }
            }
            if (d - prev < mid)
                count++;
            if (count <= n){
                ans = ans < mid ? mid : ans;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return ans;
    }
}