[Java] 징검다리*

1. 문제

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

코딩테스트 연습 - 징검다리

 

 

 

2. 풀이과정

0~distance 범위를 이진탐색을 통해 답을 찾는다.

 

매 loop마다 중간값보다 작으면 합치고, cnt를 센다.

1) cnt가 n개 이상이면, 값을 줄여야 하므로 right = m-1

2) cnt가 n개 이하면, 값을 늘려야 하므로 left = m+1

3) cnt == n이 되는 중간값은 여러 개 있을 수 있다. 그 중 가장 큰 값이 답이므로 left = m+1

 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int len = rocks.length;
        //다 없애야 될 경우
        if(len==n){
            return distance;
        }
        int s = 0, e = distance;
        Arrays.sort(rocks);
        int arr[] = new int[len+2];
        for(int i=0; i<len; i++){
            arr[i+1]=rocks[i];
        }
        arr[len+1]=distance;
        while(s<=e){
            int m = (s+e)/2;
            int start = 0, cnt = 0;
            for(int i=1; i<len+2; i++){
                if(arr[i]-arr[start]<m){
                    cnt++;
                }
                else{
                    start=i;
                }
            }
            if(cnt>n){e=m-1;}
            else{s=m+1;}//가능한 것 중 가장 큰 수
        }
        
        return e;
    }
}