📌 풀이 과정
n개의 바위를 제거한 후에 만들 수 있는 "바위 사이의 최소 거리들 중 최댓값"을 구하는 문제이다.
쉽게 말해, 바위를 제거해서 바위 사이 간격을 최대한 크게 두면서도
그 중에서 제일 작은 가격이 얼마인지 구하면 된다.
제거할 바위의 조합을 구해서 완탐으로 풀어도 될 것 같은데... 시간 초과가 난다 ㅇㅋ
그렇다면 이 문제를 어떻게 이분탐색으로 풀 수 있을까..!!!
먼저 왜 이분 탐색을 사용해야하는지 알아보자.
왜 이분 탐색을 쓸까?
0부터 도착점까지 모든 거리를 시도해보면 너무 오랜 시간이 걸리게 된다.
중간값부터 시도하면서 범위를 절반씩 좁혀가는 게 효율적이게 된다.
int low = 0 # 최소 간격의 가능한 최솟값 (바위 사이가 붙어있는 경우)
int high = distance # 최소 간격의 가능한 최댓값 (모든 바위를 제거한 경우)
int mid = (low + high) / 2 # 우리가 시도해볼 첫 번째 간격
mid 값의 의미
mid는 현재 탐색에서 시도해볼 최소 간격 이라고 생각하면 된다.
그렇다면, 이 mid값보다 작은 돌 간격의 값이 있어서는 안된다는 것이다.
mid보다 작으면 해당하는 돌을 제거하여 갯수를 세고,
mid보다 크다면 돌을 세지 않는다.
즉, 핵심 포인트는
- mid는 현재 탐색에서 시도해볼 최소 간격
- 바위를 제거하면서
- 너무 많이 제거되면 → 간격이 너무 큼 → high를 낮춤
- 더 제거 가능하면 → 더 큰 간격 가능 → low를 높임
- 이 과정에서 실제로 만들어지는 최소 간격들 중 최댓값이 정답이다.
✨ 제출 코드
public static int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks); // 바위 정렬
int left = 1;
int right = distance;
int answer = 0;
while (left <= right) {
int mid = (left + right) / 2; // 기준이 되는 최소 거리
int current = 0; // 현재 위치
int removeCnt = 0; // 제거한 바위 수
int minDistance = distance; // 현재 단계의 최소 거리
for (int rock : rocks) {
int diff = rock - current; // 현재 위치와 바위 사이 거리
if (diff < mid) {
removeCnt++;
} else {
current = rock; // 현재 위치 갱신
minDistance = Math.min(minDistance, diff);
}
}
// 마지막 바위와 도착점 사이 거리 체크
if (distance - current < mid) {
removeCnt++;
} else {
minDistance = Math.min(minDistance, distance - current);
}
if (removeCnt > n) { // 바위를 너무 많이 제거했으면
right = mid - 1;
} else { // 바위를 더 제거할 수 있으면
answer = minDistance; // 현재 최소 거리를 저장
left = mid + 1;
}
}
return answer;
}