프로그래머스 43236번
https://school.programmers.co.kr/learn/courses/30/lessons/43236

문제

---

생각하기

---

✔️ 이분탐색

동작

rocks[] 배열내의 값을 이분탐색으로 찾는게 아니라, 그냥 0에서 distance까지 전체에서 찾아야 한다.

mid가 징검다리 사이의 간격이 되서 가장 작게되는 값을 찾는다.

    public int calc(int[] rocks, int mid, int dist) {
        int ret = 0;
        int start = 0;
        
        for(int i=0; i<M; i++) {
            if(rocks[i] - start < mid) {
                ret++;
                continue;
            }
            start = rocks[i];
        }
        
        if(dist - start < mid) {
            ret++;
        }
           
        return ret;
    } // End of calc

ret가 제거한 다리의 개수가 된다. 최소가 되면 되기 때문에 -1을 찍고오는 돌아오는 mid를 가지고 return을 한다.

결과

코드

---

import java.util.*;

class Solution {
    public static int M;
    
    public int solution(int distance, int[] rocks, int n) {
        
        Arrays.sort(rocks);
        M = rocks.length;
        return binarySearch(distance, rocks, n, 0, distance);
    } // End of solution()
    
    public int binarySearch(int dist, int[] rocks, int n, int low, int high) {
        if(low > high) {
            return -1;
        }
        
        int mid = (low + high) / 2;
        int ret = calc(rocks, mid, dist);

        if(ret <= n) {
            int temp = binarySearch(dist, rocks, n, mid + 1, high);
            
            if(temp == -1) return mid;
            else return temp;
        } else {
            return binarySearch(dist, rocks, n, low, mid - 1);
        }
    } // End of binarySearch()
    
    public int calc(int[] rocks, int mid, int dist) {
        int ret = 0;
        int start = 0;
        
        for(int i=0; i<M; i++) {
            if(rocks[i] - start < mid) {
                ret++;
                continue;
            }
            start = rocks[i];
        }
        
        if(dist - start < mid) {
            ret++;
        }
           
        return ret;
    } // End of calc
} // End of Solution class