출발지점부터 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 | rocks | n | return |
---|---|---|---|
25 | [2, 14, 11, 21, 17] | 2 | 4 |
프로그래머스 고득점 kit 이분 탐색에 속하는 문제이다.
distance가 10^9 라는 데서 nlogn의 감이 온다.
이분 탐색을 할 때는
1. 무엇을 탐색할 것인지
2. 탐색의 범위가 어떻게 되는지
3. 언제 탐색을 종료할 것인지
를 정해야 한다.
또한 이분 탐색할 데이터가 오름차순으로 정렬돼 있어야 한다.
이를 바탕으로 이분 탐색을 어떻게 적용할 수 있을 지를 생각해 보자.
우리가 찾아야 할 것은 바위 n개를 제거 했을 때 바위 사이의 거리의 최솟값 중 최댓값(...)이다!
그렇다면 탐색할 것은 바위 사이의 거리
가 될 것이다.
바위 사이의 거리는 최소 0
이다. 모든 바위가 서로 붙어 있을 때이다. 반대로 최대는 distance(출발지 ~ 도착지 사이의 거리)
이다. 모든 바위를 제거했을 때 이다.
우리는 이 바위 사이의 거리를 조절해 가면서, 바위 사이 거리의 최솟값이 특정 값(이분 탐색에서의 mid)이상이 될 때 제거한 바위의 개수를 카운트 한다.
이때 제거한 바위의 개수가 문제에서 주어진 n이 될 때까지 바위 사이의 거리를 조절해 가면서 이분 탐색을 하면 된다.
요컨대, 최소 바위 사이의 거리(mid)를 두고, 이를 만족하도록 바위를 제거한다. 이때 제거한 바위의 개수가 n보다 크면 바위 개수를 줄여야 한다. 바위 개수를 줄이려면 최소 바위 사이의 거리(mid)를 줄이면 된다 반대로, 제거한 바위의 개수가 n 이하면 바위 개수를 늘려야 한다. 즉, 만족해야 할 최소 바위의 거리(mid)를 늘리면 된다.
다음 예시를 보면 더 쉽게 이해가 될 것이다.
def solution(distance, rocks, n):
answer = 0
rocks.sort()
rocks.append(distance)
dists = []
dists.append(rocks[0])
for i in range(1, len(rocks)) :
dists.append(rocks[i] - rocks[i-1])
low = 0 # 바위 사이의 최소 간격은 0
high = distance # 바위 사이의 최대 간격은 출발지~도착지
while low <= high :
mid = (low + high ) // 2 # 바위 사이의 거리의 최솟값을 mid 이상으로 만들어야 한다
removed = 0 # 제거한 바위의 개수
curDist = 0 # 현재 바위 사이의 거리
for dist in dists :
# 아직 바위 사이의 거리가 mid 이상이 되지 않았으면 바위를 제거해서 바위 사이의 거리르 늘려준다.
if curDist + dist < mid :
removed += 1
curDist += dist
# 바위 사이의 거리가 mid 이상이면 다음으로 넘어간다.
else :
curDist = 0
# 제거한 바위의 개수를 줄여야 하면 high를 줄여야 한다.
if removed > n :
high = mid - 1
else :
low = mid + 1
answer = mid
return answer
의문이 드는 점, 개선해야할 점은 댓글로 남겨주세요.
감사합니다 😽