프로그래머스 43236. 징검다리

https://school.programmers.co.kr/learn/courses/30/lessons/43236?language=python3

프로그래머스

def solution(distance, rocks, n):
    rocks.sort()  # 바위 위치를 오름차순 정렬
    rocks.append(distance)  # 도착점을 마지막 위치에 추가
    
    left, right = 0, distance  # 거리의 최소, 최대값 초기화
    answer = 0

    while left <= right:
        mid = (left + right) // 2  # 현재 탐색 중인 최소 거리(mid 처음세팅은 최댓값으로)
        prev = 0  # 이전 바위의 위치 (0부터 시작)
        remove_count = 0  # 제거할 바위의 수

        # 바위 사이의 거리가 mid 이상이 되도록 제거할 바위 수를 계산
        for rock in rocks:
            if rock - prev < mid:  # 두 바위 사이의 거리가 mid보다 작으면
                remove_count += 1  # 현재 바위(rock)를 제거해 거리를 확보
            else:
                prev = rock  # 거리가 충분하면 이전 위치 갱신

        # 바위 제거가 가능한 경우
        if remove_count > n:  # 너무 많은 바위를 제거해야 하는 경우
            right = mid - 1  # mid를 줄여 더 작은 거리를 시도
        else:  # 제거 수가 충분한 경우
            answer = mid  # 현재 mid를 답으로 갱신
            left = mid + 1  # 더 큰 거리를 탐색

    return answer

처음에 이분탐색인 줄 모르고 무식하게 반복문으로 풀려다 시간초과났었다...