다른 블로그에서는 주로 이분탐색을 중점적으로 설명하였는데,
'최솟값 x가 되려면 몇 개의 바위를 제거해야하는 가' 부분의 이해가 어려웠다.
이 부분을 중점적으로 포스팅해 보려한다.
문제
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
해결법
문제에서는 바위를 n개 없앴을 때, 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 구하라는 문제이다.
문제에서 제시한 예시대로 'n개의 바위를 없애서 최솟값 x를 만들 수 있는 가'로 접근을 하면 실행이 불가능하다.
제거할 바위를 선택하는 경우 수가 굉장히 많아서 엄청난 연산량을 필요로 하기 때문이다.
하여, 이 문제를 풀려면 문제를 반대로 생각해야 한다.
1. '최솟값 x가 되려면 몇 개의 바위를 제거해야 하는가'를 계산할 방법을 고안해야 한다.
2. 이분탐색을 통해서 목표하는 n에 해당하는 최솟값x 범위를 좁혀 나가며 최댓값을 찾아야한다.
1. 최솟값 x가 되려면 몇 개의 바위를 제거해야하는 가
아래의 예시를 가지고 '최솟값 x이 되려면 몇 개의 바위를 제거해야 하는가'를 계산해 볼 것이다.
이해를 돕기 위해 최솟값 12를 만드려면 바위를 몇 개 제거해야하는 지 계산해보고, 최솟값 11에 대해서도 계산해 볼 것이다.
출발지점과 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있다.
아래의 슬라이드에서 노드는 바위의 위치를 나타내고 간선은 각 사이 거리를 나타낸다.
최솟값 12를 만드려면 몇 개의 바위를 제거해야하는 지 계산해 볼 것이다.
우선, 시작점에서 거리가 12 미만인 바위들을 모두 제거 할 것이다.
1. 시작점과 바위2의 거리는 2이다. 12미만이므로 바위2를 제거한다.(1)
2. 시작점과 바위11의 거리는 11이다. 12미만이므로 바위11을 제거한다.(2)
3. 시작점과 바위14의 거리는 14이다. 12미만이 아니므로 제거하지 않는다.
이제부턴 바위14와의 거리가 12미만인 바위들을 제거한다.
4. 바위14와 바위17의 거리는 3이다. 12미만 이므로 바위17을 제거한다.(3)
5. 바위14와 바위21의 거리는 7이다. 12미만 이므로 바위21을 제거한다.(4)
6. 바위14와 바위25의 거리는 11이다. 12미만 이므로 바위25를 제거해야하지만, 끝점이므로 바위14를 제거한다. (5)
바위5개를 제거하였고 최솟값은 25이 되었다. 이것으로 최솟값 12를 만드려면 5개의 바위를제거해야한다는 것을 알 수있다.
그 다음으로는 최솟값 11을 만드려면 몇 개의 바위를 제거해야하는 지 계산해보자.
우선, 시작점에서 거리가 11미만인 모든 바위를 제거할 것이다.
1. 시작점과 바위2의 거리는 2이다. 제거한다.(1)
2. 시작점과 바위11의 거리는 11이다. 제거하지 않는다.
이제부터 바위11와의 거리가 11미만인 모든 바위를 제거한다.
3.바위11과 바위14의 거리는 3이다. 제거한다.(2)
4.바위11과 바위17의 거리는 6이다. 제거한다.(3)
5.바위11과 바위21의 거리는 10이다. 제거한다.(4)
6.바위11과 바위25의 거리는 14이다. 제거하지 않는다.
바위 4개를 제거하였고 최솟값은 11이 되었다. 이것으로 최솟값 11을 만드려면 최소한 4개의 바위를 제거해야한다는 것을 알 수 있다.
2. 목표하는 n에 해당하는 최솟값x 들을 어떻게 효율적으로 찾을 것인가.
이분탐색을 적용하여 탐색해야한다.
이분탐색을 이용하여 목표하는 n에 해당하는 최솟값들의 범위를 좁혀나가 최댓값을 찾는다.
이분탐색의 범위는 두 바위는 최소한 1이상 떨어져 있고, 시작과 끝점 사이에 어떤 바위도 없으면 최솟값은 총 거리가 된다.
따라서, left: 1, right: distance로 시작한다.
그리고 n개의 바위를 제거해서 만들 수 있는 최솟값x들 중 가장 큰 값을 찾는 것에 유의하여,
탐색 도중 찾은 최솟값x의 가장 큰값을 저장 해두고, 더 큰 값을 찾았을 때만 업데이트 하도록 처리한다.
코드
import Foundation
func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
var left = 1
var right = distance
var rocks = rocks.sorted{$0 < $1} //정렬
var ans = 0 //최솟값 중 가장 큰 값
while(left <= right ) {
let mid = ( left + right )/2 //목표 최솟값
var count = 0
var prev = 0
for rock in rocks {
if ( rock - prev < mid ) { //바위 사이가 목표 최솟값보다 작은지 비교
count += 1 //바위 제거
} else {
prev = rock //바위 제거 안하고, 거리 계산 기준점 변경
}
}
if distance - prev < mid { count += 1 } //바위와 끝점 사이의 거리도 비교
if count <= n {
left = mid + 1
ans = ans > mid ? ans : mid //최솟값들 중 최댓값이 답이므로
print(ans)
} else {
right = mid - 1
}
}
return ans
}