프로그래머스 징검다리 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

저는 이분탐색을 통해 문제를 해결하였습니다.

dfs를 통해 모든 경우의 n개를 제거 후를 비교하면 시간이 오래 걸릴 것이라 판단하였습니다. 그래서 이분탐색을 통해 

사이 값이 해당 값보다 작다면 합쳐서 해당 값보다 모두 크게 만들었습니다. 이때 합치는 횟수가 n보다 크다면 n개 만큼 합쳐서 최소 값이 해당 값을 만들 수 없기 때문에 false를 리턴하였습니다. 

true라면 최소값이 해당 값보다 크거나 같은 경우이기 때문에 start를 늘리고, 반대라면 end를 줄여나가면서 답을 찾아나갔습니다. 

 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        int answer = binarySearch(distance,rocks,n);
        return answer;
    }
    private static final int MAX =  1_000_000_000;
    private static int binarySearch(int distance, int[] rocks, int n){
        int start = 0;
        int end = MAX;
        int result = 0;
        while(start <= end){
            int mid = (start + end) / 2;
            if(cal(mid,distance,rocks,n)){
                start = mid + 1;
                result = mid;
            }else{
                end = mid - 1;
            }
        }
        return result;
    }
    private static boolean cal(int mid, int distance , int[] rocks, int n){
        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){
            return true;
        }else{
            return false;
        }
    }
}