징검다리 - 프로그래머스

징검다리 - 프로그래머스

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    left, right = 0, distance
    ret = 0
    while left <= right:
        min_dist = float('inf')
        tmp = 0
        removed = 0
        mid = (left + right) // 2
        for i in range(len(rocks)):
            if rocks[i] - tmp < mid:  # 돌 사이의 거리 < 최소 거리로 예상하는 값
                removed += 1  # 최소값 중에 가장 큰 값을 찾아야하기 때문에, 해당 돌 삭제
            else:
                min_dist = min(min_dist, rocks[i] - tmp)  # 최소값 갱신
                tmp = rocks[i]
        if removed > n:  # 삭제한 값이 주어진 삭제 바위 수보다 클 때
            right = mid - 1
        else:
            ret = min_dist
            left = mid + 1
    return ret