[pro] 프로그래머스 level4 43236 징검다리 (Java) - 이분탐색

[문제]

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

프로그래머스

 

[풀이]

지점과 지점 사이 거리 최솟값 중 가장 큰 값을 구해야 하므로 이를 이분탐색의 기준으로 이용할 수 있다.

지점과 지점 사이 거리 최솟값을 먼저 설정한 후, 이를 기준으로 돌을 제거해본다. 

제거된 돌이 n개보다 많다면 간격 최솟값을 줄여(high = mid-1) 돌이 더 적게 제거되도록 해야 하고, n개 이하라면 answer를 갱신해준 후, 더 큰 간격도 가능한지 확인해보기 위해 low = mid+1로 해준다.

 

그림과 함께 풀이해주신 분이 계셔서 더 쉽게 이해를 도울 수 있다. 

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        //바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return
        int low = 1;
        int high = distance;
        
        Arrays.sort(rocks);
        
        while(low<=high){
            //지점과 지점 사이 거리의 최솟값으로 설정
            int mid = (low+high)/2;
            int prev = 0;
            int count = 0;
            
            for(int i=0; i<rocks.length; i++){
                if(rocks[i]-prev < mid){
                    count++; 
                }else{
                    prev = rocks[i];
                }
            }
            
            if(count > n){
                high = mid-1;
            }
            else{
                answer = mid;
                low = mid+1;
            }
        }
        return answer;
    }
}