문제 설명
출발지점부터 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의 미친 범위(효율적인 순회 필요성 👌)
지극히 개인적이고 항상 100% 확실한 것은 아니지만 이분 탐색을 위한 큰 두가지 조건을 만족하는 듯 하다.
그렇다면 이분 탐색을 어떻게 구현하지? 답은 최소 거리 중 가장 큰 값을 출력하는 것이다. 그럴려면 일단 최소 거리를 찾아야하는데 크게 두 가지 방법으로 1) 최소거리 배열을 만든다. 2) for문을 사용해 순회하며 살펴본다.
이중 2번의 방법을 채용했다. (1은 곧 조합이라😅) 알고리즘을 간단히 설명하자면,
- 거리의 최소, 최대 값을 지정.
- 거리를 이분탐색으로 줄여나감
- 그 거리를 모든 바위들 중 만족하는 돌의 개수를 저장
n보다 많이 그 거리를 만들 수 있다면 더 줄여줌.n보다 작거나 같으면 답이 그 범위에 있으므로answer과 mid값을 비교해서 최대값을 저장.
def solution(distance, rocks, n):
answer = 0
rocks = sorted(rocks)
#만들 수 있는 거리의 최소, 최대값 지정
min_dis = 1
max_dis = distance
while min_dis <= max_dis:
remove_cnt = 0
mid_dis = (max_dis+ min_dis) // 2
prev = 0
for rock in rocks:
if (rock - prev) < mid_dis:
remove_cnt += 1
else :
prev = rock
# 마지막 돌과 도착지의 거리도 구해줘야함
#처음에 할때는 시작점(1)과 도착점(distance)의 거리를 생각하지 못해서 에러가 났었다..
if (distance - prev) < mid_dis:
remove_cnt +=1
if (remove_cnt <= n):
answer = max(answer, mid_dis)
min_dis = mid_dis +1
else :
max_dis = mid_dis -1
return answer```