def solution(distance, rocks, n):
left, right = 0, distance
ans = 0
rocks.append(distance)
rocks.sort()
while left <= right:
mid = (left+right)//2 #최솟값 후보
prev = 0
remove = 0
for rock in rocks:
if rock-prev < mid:
remove += 1 #현재 rock을 제거
else: #현재를 제거하지 않는 경우에만 prev에 현재 rock을 넣을 수 있음.
prev = rock
if remove > n:
right = mid - 1
else:
ans = mid
left = mid + 1
return ans우선, distance는 1 이상 1,000,000,000 이하 라는 조건만 보고도 이분탐색을 적용해야함을 알 수 있다.
거리 기준 이분탐색을 할건데, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값은 어떻게 구할 것이냐?
이분탐색으로 mid를 구해서, 그 mid가 답이라고 두고 검증해나간다.
(현재 mid가 조건을 만족하는 가능한 최소 거리 후보)
mid가 최솟값이면, 바위 사이의 거리가 mid보다 작은 값들은 제거된 상태여야하고 그 제거된 개수가 n개여야한다.
만약 제거된 개수가 n보다 크면 범위를 작은 숫자쪽으로 줄이고,
같거나 작으면 범위를 큰 숫자 쪽으로 줄인다.
그런데 문제 조건에 거리의 최솟값 중 가장 큰 값이라서 ans = max(ans, mid)을 해줘야 하는 것이 아닌가 싶었지만,
left = mid+1 로써 더 큰 최소 거리(left = mid + 1)를 탐색하므로, answer를 mid로 갱신하는 것만으로도 최신 상태를 유지할 수 있게된다.
