문제 출처

코딩테스트 연습 > 이분탐색 > 징검다리
https://school.programmers.co.kr/learn/courses/30/lessons/43236

문제 설명

출발지점부터 distance 만큼 떨어진 곳에 도착지점, 바위들이 있는 위치를 담으 배열 rocks, 제거할 바위의 수 n이 주어 질 때, 바위 n개를 제거 한 뒤 각 지점 사이 거리의 최솟값 중 가장 큰 값을 return 하라.

접근 방법

mid는 (left + right)/2로 설정하고, mid 보다 돌과 돌 사이의 거리가 작은 거리가 있을 경우 해당 돌을 제거한다. 그렇게 제거한 돌의 갯수가 제거해야하는 갯수 n을 넘을 경우 right = mid -1, n을 넘지 않을 경우 left = mid +1로 설정하여 최소 거리중 가장 큰 값인 mid를 찾는다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        Arrays.sort(rocks);
        int left = 1;
        int right = distance;
        
        while(left <= right){
            int mid = (left + right)/2;
            int removedStones = 0;
            int prev = 0; // 이전 돌 위치
            
            for(int rock : rocks){
                if(rock - prev < mid){ // 현재 돌과 이전 돌 사이가 mid보다 작으면 제거
                    removedStones++;
                } else{
                    prev = rock;
                }
            }
            if(distance - prev < mid){
                removedStones++;
            }
            
            if(removedStones <= n){
                answer = mid;
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        return answer;
    }
}

알게된 점

이분 탐색에서 가장 중요한 점은 찾으려는 정답의 후보이며, 최종적으로 반환해야하는 값이다.

처음엔 mid를 index로 접근하려고 해서 최댓값이 있는 범위를 제거하는 방식으로 접근 했지만, 이는 돌을 제거하지도 않고, 최솟값을 알아낼 수도 없다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        Arrays.sort(rocks);
        int left = 1;
        int right = distance;
        
        while(left < right){
            int mid = (left + right)/2;
            int left_min = 0;
            int right_min = distance;
            
            // left ~ mid 까지 돌 사이의 최소값 확인
            for(int i= left; i<mid; i++){
                if(i+1 >= rocks.length) break;
                left_min = Math.max(left_min, rocks[i]-rocks[i+1]);
            }
            for(int j = right; j>mid; j++){
                right_min = Math.max(right_min, rocks[j]-rocks[j-1]);
            }
            
            if(left_min>right_min) left = mid+1;
            else right = mid-1;
        }
        answer = rocks[left];
        return answer;
    }
}

문제푼 흔적