이분탐색 - 징검다리

해당 문제는 이분탐색을 이용한 문제로 조건에 맞는 mid를 찾아내는 방식으로 구했습니다. 조건에 맞는 mid란 mid 이상의 거리를 만드는 데 제거 되어야 하는 돌의 count를 새고 돌의 count가 입력받은 n 보다 크다면 mid의 범위를 줄이고 작다면 mid의 범위를 키우는 식으로의 이분탐색을 진행했습니다. 해당 문제는 이분탐색 카테고리에 없었다면, 알고리즘을 추측하고 문제를 풀기 어려웠을것으로 생각됩니다.

public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int[] betweenRockLengths = new int[rocks.length];
        Arrays.sort(rocks);
        betweenRockLengths[0] = rocks[0];

        for (int i = 1; i < rocks.length; i++) {
            betweenRockLengths[i] = rocks[i] - rocks[i - 1];
        }
        int left = 1;
        int right = distance;

        int currentLength;
        int removeCount;
        while(left <= right) {
            int mid = (left + right) / 2;
            currentLength = 0;
            removeCount = 0;
            for (int between : betweenRockLengths) {
                currentLength += between;
                if (currentLength < mid) {
                    removeCount++;
                } else {
                    currentLength = 0;
                }
            }
            if (removeCount > n) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            answer = (left + right) / 2;
        }

        return answer;
    }