[ Lv 4 ] [ 이분 탐색 ] 징검다리

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

코딩테스트 연습 - 징검다리

---

풀이 과정

---

1. 이분 탐색으로 풀이를 한다. 이분 탐색의 대상은 각 지점 사이의 거리의 최솟값으로 진행한다.

   • 이 값을 mid라고 두자.

2. 만약 이전 돌과 현재 돌 사이의 거리가 mid보다 작다면 제거해야되는 돌이므로 제거 카운팅을 늘려준다.

   • 맨 마지막에 도착지점과 마지막 돌 사이의 거리도 체크해줘야 함.
   • 제거한 돌은 거리 계산에 들어가면 안되므로, 이전 돌은 prev라는 변수에 따로 저장해두고 현재 돌을 제거해야되는 경우 prev 변수를 갱신하지 않도록 함.

3. 제거한 돌의 개수가 n개 이하인 경우에는 정답을 저장해 두고 오른쪽 구간 진행(최댓값을 찾아야 하므로)

4. 제거한 돌의 개수가 n개보다 많은 경우는 왼쪽 구간 진행

• 원래 문제 읽어보면 딱 n개 제거해야되는거 같은데, n개 제거하도록 하면 틀림. n개 이하로 해야 맞음..

---

소스 코드

---

def solution(distance, rocks, n):
    answer = 0
    left = 0
    rocks.sort()
    right = int(10e8)+1

    # mid를 최솟값이라고 할 때
    while left <= right:
        mid = (left + right) // 2
        prev = 0
        eliminated_count = 0
        for i in range(len(rocks)):
            if rocks[i] - prev < mid:
                eliminated_count += 1
            else:
                prev = rocks[i]

        if distance - prev < mid: # 도착 거리
            eliminated_count += 1

        if eliminated_count <= n:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer