[Level4] 징검다리

🛠 문제

https://programmers.co.kr/learn/courses/30/lessons/43236

👩🏻‍💻 해결 방법

이분탐색으로 문제를 풀기 위해서는 어떤 값을 이분탐색할지 정해야했다
여기서는 제거할 바위의 수(n)을 기준으로 범위를 설정해주었다
우선 바위를 정렬하고 거리 계산을 위해 distance를 리스트에 추가해주었다
이분탐색 과정에서는 최솟값 중의 최댓값을 구해야 했으므로 각 지점 사이의 거리가 mid 값보다 작으면 삭제를 해주고, 크면 min_distance의 값을 갱신해주었다
만약 제거된 바위의 개수가 n보다 컸다면 end 범위를 바꿔주고, 그렇지 않다면 answer에 mid 값을 저장해주었다

소스 코드

def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    rocks.append(distance)
    start, end = 0, distance
    
    while (start <= end):
        mid = (start + end) // 2
        min_distance = int(1e9)
        current = 0
        remove = 0
        
        for i in rocks:
            diff = i - current
            if diff < mid:
                remove += 1
            else:
                current = i
                min_distance = min(min_distance, diff)
        
        if remove > n:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1
                
    return answer