[프로그래머스] 징검다리

프로그래머스 징검다리

유형

• 이분탐색(Binary Search)

코드

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        // 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값
        int answer = 0;

        // 바위들을 위치별로 정렬한다
        Arrays.sort(rocks);

        // 시작점부터 끝점까지를 이분탐색해서, 찾고자 하는 값(바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값)을 탐색한다.
        // 중간값이 n개의 돌을 제거했을 때 바위 사이의 거리중 최소값이라고 가정한다면, 중간값보다 작은 돌은 제거되어야 한다.
        // (EX. 중간값이 5라면, 바위 사이의 거리가 5보다 작은 케이스는 모두 제거해야 한다. 그래야 최솟값이 5가 될 수 있기 때문)
        // 만약 제거된 돌의 개수가 n개보다 많다면, 찾고자 하는 값이 중간값보다 작음을 알 수 있다.
        // 만약 제거된 돌의 개수가 n개보다 작거나 같다면, 찾고자 하는 값이 중간값보다 클 수 있음을 알 수 있다.
        int start = 0;
        int end = distance;
        while(start <= end) {
            int mid = (start + end) / 2;
            int preRock = 0;
            int deletedRock = 0;

            for (int rock : rocks) {
                // 바위 사이의 거리가 중간 값보다 작을 경우에는, 해당 바위를 제거해준다.
                if(rock - preRock < mid) {
                    deletedRock++;
                } else {
                    preRock = rock;
                }
            }
            if(distance - preRock < mid) deletedRock++;

            // 제거해준 바위가 n보다 클 경우에는, 더 작은 값을 탐색한다.
            if(deletedRock > n) {
                end = mid - 1;
            }
            // 제거해준 바위가 n보다 작거나 같을 경우에는, 더 큰 값을 탐색한다.
            else {
                answer = mid;
                start = mid + 1;
            }
        }

        return answer;
    }
}

참고: https://deok2kim.tistory.com/122