240201 징검다리

public int solution(int distance, int[] rocks, int n) {
	Arrays.sort(rocks);
	return binarySearch(distance, rocks, n);
}

private int binarySearch(int distance, int[] rocks, int n) {
	int left = 1;
	int right = distance;
	int answer = 0;

	while (left <= right) {
		int mid = (left + right) / 2;
		int removedRockCnt = countRemovedRocks(rocks, mid, distance);

		if (removedRockCnt <= n) {
			answer = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return answer;
}

private int countRemovedRocks(int[] rocks, int mid, int distance) {
	int before = 0;
	int end = distance;
	int removeCnt = 0;

	for (int rock : rocks) {
		if (rock - before < mid) {
			removeCnt++;
		} else {
			before = rock;
		}
	}

	if (end - before < mid) {
		removeCnt++;
	}

	return removeCnt;
}

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