문제
출발지점부터 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는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.
입출력 예
| distance | rocks | n | return |
|---|---|---|---|
| 25 | [2, 14, 11, 21, 17] | 2 | 4 |
풀이
- 입력받은 rocks 배열에 출발점 (0)과 도착점 (distance) 를 추가해서 정렬한다.
- 정렬된 배열을 통해 각 지점간의 거리를 구하는 배열을 생성한다.
- 이 배열을 통해 최소 거리의 최댓값을 구한다.
- 첫 번째로 생각한 해결책 처음 문제를 보고 생각한 방식은 그리디 알고리즘이였다. 현재 가장 짧은 거리를 선택하여 해당 번째의 돌을 제거해주고 거리 배열을 최신화 시켜주는 방식으로 문제를 해결해 보려고 했다. 그러나 문제를 맞출 수 없었다. 곰곰히 생각해보니 현재의 상태의 최적의 경우가, 미래에도 최적의 선택이 아닐수도 있다는 생각이 들었다.
문제를 해결한 방법 먼저 카테고리에 이분 탐색이라고 나와있어서 이분 탐색을 적용해보기로 했다. 현재 문제에서 적용할 수 있는 것이 거리라고 생각했고, 거리의 최솟값을 0 최댓값을 입력받은 distance로 설정했다. 이후
mid = (max+min)/2로 중간값을 설정하고, 이 거리를 만족시키려고 할때 몇개의 돌을 없애야 되는지 계산한 다음 n과 없앤돌을 비교해서 최소, 최댓값을 최신화 해주었다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
let max = distance; let min = 0; let ans = 0; while (min <= max) { const mid = Math.floor((max + min) / 2); let acc = 0; let cnt = 0; for (const value of dist) { if (value + acc < mid) { acc += value; // 현재 돌을 제거하기 때문에 현재 거리를 추가해준다. cnt++; // 돌을 제거한 개수를 세어준다. } else acc = 0; // 돌을 제거하지 않아도 되기때문에 해당 순서에서 다시 거리를 측정하기 위해 acc를 0으로 초기화 해준다. } if (cnt > n) max = mid - 1; // 없앤 개수가 기준보다 크면 최댓값을 갱신 else { // 없앤 개수가 기준보다 작을 때 min = mid + 1; // 최솟값 갱신 ans = mid; // 정답에 현재 만족하는 값 입력 } }
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const solution = (distance, rocks, n) => {
rocks.push(0);
rocks.push(distance);
rocks.sort((a, b) => a - b);
const dist = [];
for (let i = 1; i < rocks.length; i++) {
dist.push(rocks[i] - rocks[i - 1]);
}
let max = distance;
let min = 0;
let ans = 0;
while (min <= max) {
const mid = Math.floor((max + min) / 2);
let acc = 0;
let cnt = 0;
for (const value of dist) {
if (value + acc < mid) {
acc += value;
cnt++;
} else acc = 0;
}
if (cnt > n) max = mid - 1;
else {
min = mid + 1;
ans = mid;
}
}
return ans;
};
이분탐색 카테고리에 있었지만 이분탐색을 사용하지 않고도 그리디 알고리즘을 통해 해결할 수 있을 것 같았지만, 현재의 최적의 경우가 전체로 보았을 때 최적이 되지 않을 수 있다는 것을 알았다.