프로그래머스: 징검다리

문제

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

 

문제 풀이

 출발지점부터 거리만큼 떨어진 곳에 도착지점이 있다. 이때 그 사이에 있는 바위들 중 몇 개를 제거하려고 한다. 특정 바위를 `N`개만큼 제거할 때 거리의 최솟값이 최대가 되는 경우를 구하는 문제이다.

 

 이 문제는 문제의 분류와 같이 `이분 탐색`으로 해결할 수 있다. `이분 탐색`을 통해 최소값 기준으로, 빠진 돌의 개수를 카운트한 후 거리의 최솟값이 최대가 되는 경우를 찾으면 된다.

 

코드

from math import inf

def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    start, end = 0, distance
    
    while start <= end:
        mid = (start + end) // 2
        prev, rock_cnt = 0, 0
        cur_min = inf
        
        for rock in rocks:
            if rock - prev < mid:
                rock_cnt += 1
            else:
                cur_min = min(cur_min, rock - prev)
                prev = rock
        
        if rock_cnt > n:
            end = mid - 1
        else:
            answer = cur_min
            start = mid + 1
                
    return answer