징검다리 이분탐색

프로그래머스 lev.4 징검다리 이분탐색 문제이다.

핵심은 징검다리 배열을 순회하면서 내가 이 징검다리를 지웠을 때, 만들어지는 거리가 얼마인가? 를 파악하는 것이다.

예전에도 정리한 적이 있었는데, 이분탐색이 개념 자체는 심플하지만, 그 내부에서 반드시 함수가 필요하고, 이 함수를 구현하는 것이 쉽지 않다고 했다.

문제를 보면 내가 지워야 할 바위 개수 n이 주어지는데, 내가 이분탐색할 거리를 징검다리를 없애면서 생기는 거리와 비교하면서 징검다리를 없앴을 때 생기는 그 사이의 거리가 이분탐색할 거리가 더 작다면, 나는 징검다리를 더 치워야 한다는 뜻이다.

그러므로 징검다리를 치우는 크기를 count 라고 했을 때, count > n 이라면 너무 과하게 많이 치웠다는 뜻이므로, 이분탐색할 거리를 줄여야 하고, 그 반대라면 이분탐색할 거리를 늘려야 한다.

또한 징검다리를 순회하면서 거리를 찾아내는 로직도 구현해야 하는데, 이건 구현에 가깝다.

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    rocks.insert(0, 0)
    # 먼저 0과 첫번째 징검다리와 마지막의 거리도 구해주어야 하므로 해당 로직
    
    left, right = 0, distance
    answer = -1
    
    while left <= right:
        mid = (left + right) // 2
        count = 0
        j = 0 # 비교대상 징검다리
        i = j + 1 # 내가 치워버릴수도있는 징검다리
        while i < len(rocks): # rock을 모두 순회하면서
            if rocks[i] - rocks[j] < mid: # 징검다리의 차이가 탐색중인 거리보다 작으면
                i += 1 # 징검다리를 치워버리고 거리를 벌린다.
                count += 1
                continue
                # 만약 거리가 탐색중인 거리보다 커졌으면 다음 징검다리 탐색
            j = i
            i += 1
        if count <= n: # 최대값을 찾기 위한 이분탐색 조건
            answer = max(answer, mid) # 최대값 저장
            left = mid + 1
        else:
            right = mid - 1

    return answer