문제

문제 설명

출발지점부터 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

입출력 예 설명

문제에 나온 예와 같습니다.

풀이

문제 이해
도착지점까지의 거리 distance가 25일 때
[2, 14, 11, 21, 17] 위치에 바위가 있다.
여기서 [2, 14]를 제거하면,

0 ~ 11 ~ 17 ~ 21 ~ 25
  11   6    4    4

이렇게 11, 6, 4, 4씩 차이가 나서 최솟값은 4가 된다.
무얼 제거하고 나서 나오는 최솟값은 2, 3, 3, 2, 4 이렇게 나온다.
이 중 가장 큰 값은 4이므로 4를 리턴한다.
=> 이런식으로 무얼 제거하고 나서 나오는 최소값들 중 가장 큰 값을 리턴하면 된다.

입력값

• distance: 출발지에서 도착지까지의 거리
• rocks: 중간에 놓여 있는 바위들의 위치 리스트
• n: 제거할 수 있는 바위 개수

이진 탐색으로 진행할 것이다. (다른 사람의 풀이를 참고했다.)
1. 1을 left로, distance를 right로 설정한다.

left = 1
right = distance

2. 바위 위치 정렬이 필요하다.
   rocks.sort()

3. 도착 지점도 sort의 가장 끝 부분에 넣어준다.
   `rocks.append(distance)

4. 이진 탐색을 진행한다.

    while left <= right:
        mid = (left + right) // 2 # 징검다리 사이 최소 거리 후보 (답이 될 수 있다)
        
        delete = 0 # 제거한 바위 개수
        prev_rock = 0 # 이전 바위의 위치
        
        for rock in rocks: # 정렬된 돌을 돌면서
            dist = rock - prev_rock # 현재 바위에서 이전 바위까지 거리
            
            if dist < mid: # 거리가 커트라인 보다 작다면(최솟값을 구해야 하므로)
                delete += 1 # 바위를 제거
                
                if delete > n: # 제거할 바위의 수 초과한다면 break. 더 작은 mid값이 필요하다
                    break
            
            else: # 바위를 제거하지 않았다면
                prev_rock = rock # 현재 바위를 이전 바위로 갱신
                
        # 제거할 바위의 수 초과한 경우 : 더 작은 mid값이 필요하다
        if delete > n:
            right = mid - 1
        # 제거할 바위의 수 이하인 경우 : 정답이거나 더 큰 mid값이 필요하다
        else:
            answer = mid # 답이 될 수 있다!
            left = mid + 1

최종 코드

def solution(distance, rocks, n):
	# 이진탐색 처음 범위 : 1 ~ distance
    left = 1
    right = distance
    
    # 바위 위치 정렬, 도착지점 가장 끝에 추가
    rocks.sort()
    rocks.append(distance)
    
    while left <= right:
        mid = (left + right) // 2 # 징검다리 사이 최소 거리 후보 (답이 될 수 있다)
        
        delete = 0 # 제거한 바위 개수
        prev_rock = 0 # 이전 바위의 위치
        
        for rock in rocks: # 정렬된 돌을 돌면서
            dist = rock - prev_rock # 현재 바위에서 이전 바위까지 거리
            
            if dist < mid: # 거리가 커트라인 보다 작다면(최솟값을 구해야 하므로)
                delete += 1 # 바위를 제거
                
                if delete > n: # 제거할 바위의 수 초과한다면 break. 더 작은 mid값이 필요하다
                    break
            
            else: # 바위를 제거하지 않았다면
                prev_rock = rock # 현재 바위를 이전 바위로 갱신
                
        # 제거할 바위의 수 초과한 경우 : 더 작은 mid값이 필요하다
        if delete > n:
            right = mid - 1
        # 제거할 바위의 수 이하인 경우 : 정답이거나 더 큰 mid값이 필요하다
        else:
            answer = mid # 답이 될 수 있다!
            left = mid + 1
    return answer