[Algorithm] 프로그래머스 - 징검다리 python

진짜 오랜만에.. 블로그 포스팅.. 킁냐
간만에 이분탐색 문제를 풀어봤는데 접근 방법이 쉽지 않았어서 기록하려고 한다.

문제

출발 지점부터 distance만큼의 공간이 있고 그 사이에 바위(rocks)가 존재한다.
이때 n의 바위를 제거해을 때, 각 바위 사이의 거리의 최솟값 중에 가장 큰 값을 구하는 문제이다.

접근 방식

일단 바위의 개수가 1개 이상 - 50,000개 이하라 n개를 뽑아 삭제 후 최솟값을 찾는 건 불가능일 것 같다는 생각이 들었음. ㅋㅋ게다가 카테고리가 이분 탐색임. 그래서 이분 탐색 고고

그런데 이분 탐색을 어디다가 적용해야하는지 감을 잡기가 어려웠음.

자 문제 정의 먼저 해보자고
바위 n개를 제거한 뒤 각 바위 사이 거리의 최솟값을 리턴해야함.
각 바위 사이 거리의 범위는 0 ~ distance일 것임.

그럼 각 바위 사이 거리중에 최솟값을 mid로 두고, 이 값이 바위 사이의 최솟값이라면 x개의 바위를 삭제할 수 있을 것임.
그럼 최종적으로 삭제된 x와 n을 비교 후 mid의 값을 조정해주면서 탐색을 지속함.

코드

def solution(distance, rocks, n):
    rocks.append(distance) # 맨 마지막 바위를 넣어줌 (맨 뒤 거리도 계산)
    rocks.sort()

    left, right = 0, distance
    while left <= right:
        mid = (left + right) // 2  # 거리 최솟값

        prev, count = 0, 0
        min_distance = distance
        for rock in rocks:
            d = rock - prev # 현재 바위 - 이전 바위 (사이 거리)
            if d < mid:  # 삭제 (mid보다 작으면 mid가 최솟값일 수 없음)
                count += 1
            else:
                min_distance = min(min_distance, d)
                prev = rock

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

    return answer


solution(25, [2, 14, 11, 21, 17], 2)
solution(16, [4, 8, 11], 2)