## 의사 코드 ##
# 탐색 범위가 100만 이상 -> 이분탐색
# 이분탐색 전제 조건: 정렬
# rocks.sort()
# left = 0
# right = distance
# 현재 거리 => 각 바위 사이의 거리의 최솟값 중 가장 큰 값
# mid = (left + right) // 2
# 현재 제거한 바위의 수
# delete = 0
# 이전 바위의 위치
# prev_rock = 0
# 바위 사이의 거리를 구했을 때 mid 보다 작으면 제거, 크면 그대로 두기
# for rock in rocks:
# dist = rock - prev_rock
# if dist < mid: delete += 1
# else: prev_rock = rock
# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 탐색 범위를 작은 쪽으로 줄이기
# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작으면 탐색 범위를 큰 쪽으로 줄이기
통과한 코드
def solution(distance, rocks, n):
answer = 0
# 바위의 위치 오름차순 정렬
rocks.sort()
left, right = 0, distance
while left <= right:
# 현재 거리 => 각 바위 사이의 거리의 최솟값 중 가장 큰 값
mid = (left + right) // 2
# 현재 제거한 바위의 수
delete = 0
# 이전 바위의 위치 (시작: 시작지점인 0)
prev_rock = 0
for rock in rocks:
# 현재 바위와 이전 바위 사이의 거리
dist = rock - prev_rock
# 바위 사이의 거리가 mid보다 작으면 바위 제거
if dist < mid:
delete += 1
# 바위 사이의 거리가 mid보다 같거나 크면 이전 바위의 위치를 현재 바위 위치로 변경
else:
prev_rock = rock
# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 break
if delete > n:
break
# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 탐색 범위를 작은 쪽으로 줄이기
if delete > n:
right = mid - 1
# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작으면 탐색 범위를 큰 쪽으로 줄이기
else:
answer = mid
left = mid + 1
return answer
과정 확인
distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2
"""
left: 0, right: 25
현재 거리(mid): 12
현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2
현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11
현재 바위의 위치: 14, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 14
현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 제거한 바위의 수(delete): 3
<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많은 경우
갱신된 right: (mid - 1) = 11
------------------------------
left: 0, right: 11
현재 거리(mid): 5
현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2
현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11
현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 17, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 6
현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4
현재 제거한 바위의 수(delete): 3
<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많은 경우
갱신된 right: (mid - 1) = 4
------------------------------
left: 0, right: 4
현재 거리(mid): 2
현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2
현재 바위의 위치: 11, 이전 바위의 위치: 2
현재 바위와 이전 바위 사이의 거리(dist): 9
현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4
현재 제거한 바위의 수(delete): 0
<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 3
------------------------------
left: 3, right: 4
현재 거리(mid): 3
현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2
현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11
현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4
현재 제거한 바위의 수(delete): 1
<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 4
------------------------------
left: 4, right: 4
현재 거리(mid): 4
현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2
현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11
현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3
현재 바위의 위치: 17, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 6
현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4
현재 제거한 바위의 수(delete): 2
<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 5
------------------------------
4
"""