1
def solution(distance, rocks, n):
2
    answer = 0
3
    rocks.sort()
4

5
    # bs의 탐색 대상 = rock 거리 간의 최소값
6
    left, right = 0, distance
7

8
    while left <= right:
9
        removeRockCnt = 0
10
        mid = int((left + right) / 2)
11
        minDistance = float('inf')
12

13
        # 현재 어느 돌에 있는지 저장
14
        current = 0
15

16
        for rock in rocks:
17
            diff = rock - current
18
            # 실제로 rocks 배열을 조작하지 않고
19
            # current를 변경해주는 것으로 삭제할 돌을 선택한다.
20
            if diff < mid:
21
                # current를 저장하지 않고 건너뛰어서 마치 돌을 삭제한 효과를 기대
22
                removeRockCnt += 1
23
            else:
24
                current = rock
25
                # 삭제하지 않을 돌이기 때문에 거리의 최소값 계산
26
                minDistance = min(minDistance, diff)
27

28
        # n보다 더 많이 지웠다면 더 적게 지워야한다.
29
        # 즉, 돌들간의 거리의 최소값이 더 작아져야하므로 right를 감소
30
        if removeRockCnt > n:
31
            right = mid - 1
32
        # n보다 더 적게 지우거나 같다면 answer를 일단 저장한다.
33
        # 두 경우는 문제의 답을 내포한 경우이기 때문이다.
34
        else:
35
            answer = minDistance
36
            # n보다 더 적거나 같게 돌을 지웠으므로
37
            # 거리의 최소값을 늘려서 지울 돌의 개수를 늘려야한다.
38
            left = mid + 1
39

40
    return answer