징검다리

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항
도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.

문제를 처음 봤을때 가장먼저 정렬해서 하나씩 빼서 해결한다면 해결될것 같았지만 그렇게 한다면 시간 초과가 걸린다. 너무 많은 경우의 수를 해야하기 때문이다.

이 문제는 이분탐색을 할줄아느냐 묻는 문제였다.

먼제 둘로 나눠야하는것은 바위사이의 거리이다. 단 첫시작점과 마지막 부분도 추가해야한다.
이후 각 사이의 거리를 구했다면 최솟값과 최댓값을 잡아 돌을 제거해나간다.
만약 제거되는 돌의 개수가 실제 제거할수있는 돌의 개수 보다 많다면 불가능하다는 이야기이므로 max값을 mid -1로 줄인다.
반대로 가능하다면 min값을 mid + 1로 높여서 범위를 줄여가는 방식을 사용하면된다.

마지막으로 최소의 값을 원하는 것이였으므로 현재가능한 min값과 저장되어있는 answer의 값으로 비교하여 결과를 내면 된다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        int[] width = new int [rocks.length+1];
        
        //각 사이 거리구하기
        width[0]=rocks[0];
        width[width.length-1]=distance-rocks[rocks.length-1];
        for(int i=1;i<rocks.length;i++){
            width[i]=  rocks[i] - rocks[i-1];
        }
        //이분문제 
        int min =1;
        int max =distance;
        while(min<=max){
            int remove=0;
            int sum =0;
            int mid = (min+max)/2;
            for(int i=0;i<width.length;i++){
                sum+=width[i];
                if(sum<mid){
                    remove++;
                    continue;
                }
                sum=0;
            }
            if(remove>n){
                max = mid-1;
                continue;
            }
            min = mid+1;
            answer= Math.max(answer,mid);
        }
        
        
       
        return answer;
    }
}//이분문제 바위를 지울때마다 정렬해서 한다면 시간내에 해결하지못함.

이분문제여서을 직접 제거하지않는다는것을 깨닫지 못하면 시간초과를 계속 당하는 문제였다.