🗃️문제 설명
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
👉제한사항을 참고하면 바위는 1개 이상, 50000개 이하로 명시 → 만약 50000개의 바위 중에서 25000개의 바위를 선택해 제거한다면 그 경우의 수를 nCr로 계산하면 매우 큰 수가 나오게 된다.
👉따라서 조합으로는 해결을 할 수 없는 문제다. 최소 거리를 이진 탐색으로 구하는 방법으로 생각한다. 시작 지점은
0, 도착 지점은distance이다. 바위 간의 거리를 for문으로 탐색하면서 만약 최소 거리보다 값이 작다면 그 바위는 제거 대상에 포함되므로 제거 카운트를 늘리고 만약 최소 거리보다 값이 크다면 이전 바위 위치를 갱신해준다. for문을 도는 과정에서 만약 n개보다 많은 수의 바위를 제거하게 된다면 불필요한 연산을 줄이기 위해break문을 실행시킨다.
🖥️코드
def solution(distance, rocks, n):
rocks.append(distance) # 마지막 바위와 도착 지점 사이를 고려하기 위해 추가
rocks.sort() # 바위 정렬 O(N log N)
answer = 0
left = 0
right = distance
while left <= right:
prev = 0
removed = 0
mid = (left + right) // 2
for rock in rocks:
if rock - prev < mid:
removed += 1
else:
prev = rock
if removed > n:
break
if removed > n: # 제거한 바위의 개수가 n개보다 많다면?
right = mid - 1
else:
answer = mid
left = mid + 1
return answer