[Python] 징검다리

💻 문제 정의

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.

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

제거한 바위의 위치 각 바위 사이의 거리 거리의 최솟값

[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

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

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

💡 접근 및 설계

이분 탐색을 이용하여 각 지점 사이의 거리의 최솟값 후보들의 범위를 줄여나간다.

✏️ 알고리즘 풀이

left = 1
right = distance

while left <= right:
    mid = (left + right) // 2 # 가능한 최솟값 후보
    remove_cnt = 0 # 제거한 돌의 수
    curr = 0 # 현재 위치
    
    for r in rocks:
        if r - curr < mid:
            remove_cnt += 1
        else:
            curr = r
    
    if remove_cnt > n:
        right = mid-1
    else:
        left = mid+1
        answer = mid

현재 위치에서 부터 다음 바위까지의 거리를 계산하여 최솟값 후보보다 크다면 다음 바위로 넘어가고, 후보값보다 작다면 돌을 하나 제거해서 바위 사이 거리를 크게 만든다.

이후 모든 지점의 거리가 mid값 보다 커졌을때(즉, mid가 현재의 돌 다리 상태에서 최솟값일때), 제거한 돌의 수가 n개보다 크다면 현재의 경우는 가능하지 않은 경우이므로 전체 범위를 mid-1 까지 축소한다.

만약 돌을 n개 또는 그 이하로 지웠을 경우, 현재 상태의 각 바위 사이의 거리의 최솟값 보다 큰 값이 존재하는지 확인하기 위해 시작 범위를 mid+1 이상으로 지정하고 answer에 mid를 저장해놓는다.

최종적으로 탐색이 끝난 후의 answer값이 각 바위 사이의 거리의 최솟값 중 최댓값이 된다.

🗒️ 최종 제출 코드

from itertools import combinations

def solution(distance, rocks, n):
    answer = 0
    rocks.append(distance)
    rocks.sort()
    
    left = 1
    right = distance
    
    while left <= right:
        mid = (left + right) // 2 # 가능한 최솟값
        remove_cnt = 0 # 제거한 돌의 수
        curr = 0 # 현재 위치
        
        for r in rocks:
            if r - curr < mid:
                remove_cnt += 1
            else:
                curr = r
        
        if remove_cnt > n:
            right = mid-1
        else:
            left = mid+1
            answer = mid
        
    return answer

---

💭 오늘의 회고

-