프로그래머스(이분탐색)-징검다리-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 함수를 작성해주세요.

제한사항

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

입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

 

---

내 문제풀이

1. 바위 사이 거리를 기준으로 이진탐색을 수행한다. 가능한 바위 사이 거리는 대략 0~1000000000으로 두고 최솟값을 left, 최댓값을 right로 설정한다.

2. mid는 현재 turn에서의 최소 바위 사이 거리이다. 이 보다 작을 수는 없으며, 크거나 같을 수는 있다.

3. rocks를 하나 씩 보며 각 바위 사이의 거리와 mid를 비교한다.
mid보다 작은 경우, 뒷 바위(현재 위치)를 제거하는 것으로 판단하여 count(제거한 바위 갯수) +1 한다.
이 외의 경우, 현재 turn에서 바위 사이 거리의 최솟값(변수 dist)을 계산하고 앞 바위를 현재 위치로 이동시킨다.

4. 모든 바위를 모두 탐색 후,
count가 n보다 크다면 더 적은 바위를 제거해야 하므로, mid를 줄이기위해 right = mid-1로 설정한다.
count가 n보다 작거나 같다면 더 많은 바위를 제거해야 하므로, mid를 늘리기위해 left = mid+1로 설정한다. 추가적으로 우리는 각 turn에서의 최소 바위 거리 중 "최댓값"을 구해야 하기 때문에 mid를 늘릴 때 answer을 현재 turn의 최소 바위 거리(변수 dist)를 재설정한다.

5. 이진탐색이 종료되면 answer를 반환한다.

내 코드 - 파이썬

def solution(distance, rocks, n):
    answer = 0
    left, right = 0, distance
    rocks.sort()
    rocks.append(distance)
    
    while left <= right:
        dist = 1000000000
        mid = (left+right)//2 #현재 지정한 최소 바위 사이 거리
        count = 0 # 제거한 바위 갯수
        now = 0 #앞 바위
        
        for rock in rocks: #뒷 바위
            #현재 mid를 최소라고 가정했으므로, 더 작으면 뒷 바위 삭제
            if rock-now < mid:         
                count +=1 
            else:
                dist = min(dist, rock-now)
                now = rock
                
        if count > n:
            right = mid-1
        else:
            left = mid+1
            answer = dist #최솟값 중 최댓값이므로 바위 거리를 더 키워야하는 경우 저장
            
    return answer