문제출처: https://programmers.co.kr/learn/courses/30/lessons/43236
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
제거한 바위의 위치 | 각 바위 사이의 거리 | 거리의 최솟값 |
---|---|---|
[21, 17] | [2, 9, 3, 11] | 2 |
[2, 21] | [11, 3, 3, 8] | 3 |
[2, 11] | [14, 3, 4, 4] | 3 |
[11, 21] | [2, 12, 3, 8] | 2 |
[2, 14] | [11, 6, 4, 4] | 4 |
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다. 출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
이 문제는 바위간의 거리를 기준으로 이분탐색법을 통해 풀었는데, 사실 처음에 바위간의 거리를 따로 리스트에 저장하고 거기서 최소값을 차례로 삭제하고 합쳐주는 단순한 방법으로 풀어보려다가 도저히 통과가 안되서 결국 이분의 풀이를 참고했다...
풀이과정은 아래와 같다.
class Solution {
public int solution(int distance, int[] rocks, int n) {
int answer = 0;
Arrays.sort(rocks); //바위 거리순으로 정렬
int min = 1;
int max = distance;
int maxDist = 0;
// 바위의 거리를 기준으로 이진탐색
// mid 보다 거리가 적은 바위를 지웠을때 지운 바위의 수가 n보다 작거나 같아야한다
while(min <= max) {
int mid = (min + max) / 2;
int cnt = 0;
int prev = 0;
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < rocks.length; i++) {
if (rocks[i] - prev <= mid) {
cnt++;
}
else {
minDist = Math.min(rocks[i] - prev, minDist);
prev = rocks[i];
}
}
//마지막 바위는 그 전의 돌과 도착지점을 모두 확인해야함
if (distance - prev <= mid) {
cnt++;
}
else {
minDist = Math.min(distance - prev, minDist);
}
if (cnt <= n) {
maxDist = Math.max(maxDist, minDist);
min = mid + 1;
}
else {
max = mid - 1;
}
}
return maxDist;
}
}