출발지점부터 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 함수를 작성해주세요.
바위의 개수
이하입니다.distance | rocks | n | return |
---|---|---|---|
25 | [2, 14, 11, 21, 17] | 2 | 4 |
각 지점 사이의 거리의 최솟값
을 기준으로 이분탐색을 진행한다.distance
의 최솟값인 1, right는 distance
의 최댓값인 10억이다.isAvailable()
에서 rocks
배열을 차례대로 탐색하며 target
을 만들기 위해 돌을 제거한다.n
이하이면 available한 것이다.distance
에 대해 이분탐색을 계속 진행한다.answer
가 최솟값 중 최댓값이 된다.이번 문제에서는 isAvailable()
메소드를 내 스스로 힘으로 만들어내지 못했다.. 슬프다..
rocks
에서 돌을 직접 빼면서 removalCount
를 체크한다는 발상이 정말 경이로울 정도다. 어떻게 하면 이렇게 뚝딱 떠올릴 수 있는 걸까... 이걸 검색해서 풀 수밖에 없었던 나의 실력이 한탄스러울 뿐이다.
또 지금 생각해보면 최댓값 중 최솟값
이라는 말에 힌트가 있는 것 같다. 최댓값은 solution()
의 이분탐색 while
문 안에서 찾는 것이기 때문에 isAvailable()
에서는 최솟값을 찾아 주면 되었기 때문이다.
import java.util.Arrays;
class Solution {
private static int MIN_DISTANCE = 1;
private static int MAX_DISTANCE = 1000000000;
public int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks);
int left = MIN_DISTANCE;
int right = MAX_DISTANCE;
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (isAvailable(distance, rocks, n, mid)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
private boolean isAvailable(int distance, int[] rocks, int n, int target) {
int removalCount = 0;
int previous = 0;
for (int rock : rocks)
if (rock - previous < target) removalCount++;
else previous = rock;
if (distance - previous < target) removalCount++;
return removalCount <= n;
}
}