징검다리

프로그래머스

방법
1. 이분탐색을 위해 정렬
2. 시작을 0 끝을 거리로 두고 절반을 가지고 비교. 0과 25로 두고 가운데 값 12로 시작을 한다고 가정. 답이 12라면 바위를 n개 제거했을 때 최소거리가 12인 것이 있어야 한다.
3. 만약 12보다 작으면 그 바위는 제거한 것이므로 제거한 개수를 세기 위해 카운트 업한다.
4. 제거한 수가 n보다 크면 너무 많이 제거한 것이므로 최소거리를 줄이기 위해 end = mid-1. 그 외의 경우에는 start = mid+1

def solution(distance, rocks, n):
    
    rocks.append(distance)
    rocks.sort()
    
    start = 0
    end = distance
    answer = 0
    
    while start<=end:
        mid = (start+end)//2
        
        now = 0
        for rock in rocks:
            if rock - now < mid:
                cnt += 1
            else:
                now = rock
        
        if cnt > n:
            end = mid-1
        else:
            answer = mid
            start = mid+1
            
    return answer

reference