[코테] 프로그래머스 이분탐색 징검다리

징검다리

문제 링크

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

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

문제 풀이

left는 0, right는 도착지점까지의 거리, mid는 중간의 값을 초기값으로 해서 거리의 최솟값을 기준으로 이분 탐색을 진행한다.

만약 설정한 mid값으로 제거하는 바위가 n보다 많을 경우 right를 줄이고, n보다 클 경우는 left를 늘이는 식으로 이분 탐색을 진행하면 된다.

def get_remove_cnt(distance: int, rocks: list, mid: int) -> int:
    prev_rock = 0
    cnt = 0

    for i in range(len(rocks)) : 
        if rocks[i] - prev_rock < mid : 
            cnt += 1
            continue
        prev_rock = rocks[i]

    if distance - prev_rock < mid : 
        cnt += 1

    return cnt


def solution(distance, rocks, n):
    answer = 0
    left, right = 0, distance
    rocks.sort()
    
    while left <= right : 
        mid = (left+right) // 2
        if get_remove_cnt(distance, rocks, mid) <= n :
            answer = mid
            left = mid + 1
        else :
            right = mid - 1        
    
    return answer