[programmers/python] 징검다리 - 이분 탐색으로 바위 사이 최소 거리의 최댓값 찾기

문제 설명

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

출발지점과 도착지점 사이에 바위들이 놓여 있다. 바위는 특정 위치에 존재하며, 이 중 n개를 제거할 수 있다. 이때 출발, 바위, 도착 사이의 거리 중 최솟값을 최대화하는 것이 목표이다.

예를 들어 다음과 같은 입력이 주어진다:

distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2

• 도착지점까지의 총 거리: 25
• 바위는 위 위치에 존재
• 바위 2개를 제거할 수 있음

우리는 바위 사이의 거리 중 최솟값이 가장 크도록 바위를 제거해야 한다.

---

핵심 아이디어

이 문제는 다음 질문으로 바꿔 생각할 수 있다:

어떤 최소 거리 x가 주어졌을 때, 그 거리 이상을 유지하기 위해 바위를 몇 개 제거해야 하는가?

 

이 질문에 답할 수 있으면, 거리 x를 이분 탐색으로 조정하면서조건을 만족하는 가장 큰 x를 찾을 수 있다.

---

이분 탐색 흐름

1. 정답이 될 수 있는 최소 거리의 범위는 1 ~ distance이다.
2. 중간값 mid를 기준으로 바위를 제거해가며,
   바위 사이 거리가 mid 이상이 되도록 유지해본다.
3. 제거한 바위 수가 n 이하라면 → 조건 만족 → 거리 늘리기
4. 제거 수가 너무 많으면 → 조건 불만족 → 거리 줄이기

---

구현 코드

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    left, right = 1, distance
    answer = 0

    while left <= right:
        mid = (left + right) // 2
        prev = 0
        remove = 0

        for rock in rocks:
            if rock - prev < mid:
                remove += 1  # 간격이 부족하면 바위 제거
            else:
                prev = rock  # 바위를 유지한 경우 기준 위치 갱신

        if remove > n:
            right = mid - 1  # 너무 많이 제거함 → 거리 줄이기
        else:
            answer = mid     # 조건 만족 → 거리 늘릴 수 있는지 확인
            left = mid + 1

    return answer

---

예시 흐름

distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2

1. 정렬 → [2, 11, 14, 17, 21, 25]
2. 예를 들어 mid = 4일 때:
   • 거리 4 이상이 되도록 유지하려면 바위 2개만 제거하면 가능
   • 조건 만족 → 더 큰 거리로도 가능한지 확인

최종적으로 반환되는 값은 4이며, 이는 바위 사이 거리의 최솟값 중 최대값이다.