[프로그래머스] 징검다리- JAVA(자바)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

코드:

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; // mid: 가능한 최소 거리
            if(countRemovedRocks(mid, distance, rocks) <= n){
                left = mid + 1;
                answer = mid;
            }else{
                right = mid - 1;
            }
        }
        return answer;
    }
    
    
    public int countRemovedRocks(int min, int distance, int[] rocks){
        int cnt = 0; // 최소 거리가 min일 때 제거해야 할 돌의 개수
        int cur = 0; // 기준이 되는 돌의 위치
        for(int rock : rocks){
            if(rock - cur < min) cnt++;
            else cur = rock;
        }
        if(distance - cur < min) cnt++;
        return cnt;
    }
}
//시간 복잡도: log(distance) * rocks = log(10억)*50,000

 

countRemovedRocks(mid, distance, rocks) < n 인 경우에도 answer = mid 인 이유:

ex) 시작 : 0, 바위들 : [2, 4, 6, 8, 10], 끝 : 12, 제거 바위 수(n) : 2

원래는 n개의 바위를 제거했을 때 비로소 최소 간격의 최댓값이 결정되지만 위와 같은 경우 n개의 바위를 제거하기 전에 최소 간격(2)이 최대 구간이 된다. 그래서 while 문이 진행되어 left = 2, right = 2, mid(최대 간격) = 2 일 때, answer == 0(제거 바위 수) 이 되고 다음 while 문에서는 반복문을 벗어나게 된다. 즉, n 보다 작을 때 최대 간격이 나올 수 있기 때문에 countRemovedRocks(mid, distance, rocks) <= n 이 된다.