징검 다리 - 이진 탐색 (파이썬)

사이트 링크 : https://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 이상 바위의 개수 이하입니다.

문제 해결 포인트 

• 백준에 공유기 푸는 문제와 거의 동일합니다.
• prev_value 를 미리 선언하여 이전 제거한 거리의 값을 저장해둡니다
• mid_distance 가 mid 보다 작을경우 remove_cnt(제거한 바위수)를 올리고 제거한 값이 n 보다 클경우 반복문을 나옵니다.
• 현재 저장되어있는 최적값(result)와 mid_distancde 값이랑 비교하여 최소값을 저장합니다. 
• prev_value 를 선언하기까지 아이디어을 내는것이 힘든 문제였습니다. 

정답코드 

def solution(distance, rocks, n):
    answer = 0
    left = 1
    rocks.sort()
    right = distance
    while left <= right:
        mid = (left+right) // 2
        prev_value = 0
        # 제거할 바위 카운트
        remove_cnt = 0
        # 최대 길이 
        result = 10000000001
        for rock in rocks:
            mid_distance = rock - prev_value
            if mid_distance < mid:
                remove_cnt += 1
                if remove_cnt > n:
                    break
            else:
                result = min(result,mid_distance)
                prev_value = rock
        if remove_cnt > n:
            right = mid-1
        else:
            answer = result
            left = mid + 1
    return answer

 

현재 코드를 자주 리뷰하여 정교한 코드를 만드는 방법도 좋을듯 합니다.