해당 문제는 전형적인 이분 탐색 문제이다. 이분 탐색 문제 같은 경우 최솟값을 최대화하는 문제라던가, 최대값을 최소화하는 문제가 많다. 그리고 문제에서 주어진 제한 사항을 보면 바위의 개수가 50,000개라는 점은 O(n2) 알고리즘으로는 풀 수 없다는 것이고 적어도 O(N) , O(NlongN) 으로 풀 수 있다는 것이다. 특히 가장 의심스러운 부분은 distance가 1,000,000,000 이하라는 점이다. 대부분의 이분 탐색 문제는 이렇게 제한 사항 중에 큰 값들이 많이 등장한다. 그리고 이분탐색은 O(NlogN) 의 시간 복잡도를 갖기 때문에 충분히 효율성 검증도 통과할 수 있다.
이분탐색이 처음이라면 이분탐색 공부하러 가기
여기까지 이 문제가 이분탐색을 이용해야겠다고 생각했으면 이제 어떻게 문제를 풀어야 할 까를 생각하는 것이다. 기본적인 이분 탐색 문제 풀이 형태는 모두 똑같다. low , high를 설정하고, check함수를 만든 다음 , return 값을 선택하는 것이다.
먼저 무엇을 이분 탐색 할 것인지를 정하는 것이 중요하다. 우리가 탐색하는 것은 돌 사이의 최소 거리를 최대하는 간격을 구하는 것이다. 즉 우리는 target을 돌 사이의 최소 간격으로 할 것이다. 예를 들어 target이 10이라고 한다면, 우리는 돌들을 최대 n개까지 제거해서 돌들간의 간격이 우리의 target보다 작거나 같은지를 검사하면 된다. 여기서 작거나도 포함되는 이유는 우리의 목적은 target이 유효한지를 검사하는 것이기 떄문이다. 예를 들어 target이 10인데 돌들을 빼고 보니까 최소 간격이 8이 나왔다면, 이건 오히려 우리한테 떙큐라는 것이다. 10이여도 문제가 없구나가 되는 것이다.
만약 모든 돌을 제거한다면 우리가 얻을 수 있는 최대한의 거리는 distance가 될 것이다. 하지만 우리는 n개의 돌만 제거할 수 있다. 따라서 돌을 처음부터 제거하면서 돌 사이의 간격이 target 이상일 때까지 제거한다. 그리고 해당 위치에서 다시 다음 돌까지의 거리를 판단한다. 그리고 이를 반복한다.
여기까지 idea이고 check함수를 구체적으로 정의하면 다음과 같다.
check(targetMinimumDistance, rocks, n) -> boolean
돌을 최대 n개 까지 제거해서 각 돌들 사이의 간격이 targetMinimumDistance보다 작으면 True, 돌을 n개 초과해서 빼야하거나 불가능하다면 False.
def solution(distance, rocks, n):
answer = 0
rocks.sort()
rocks.append(distance) # 마지막 위치까지도 거리를 고려해야 하기 때문
low = 0
high = distance + 1
while low + 1 < high:
mid = (low + high) // 2
if check(mid, rocks, n):
low = mid
else:
high = mid
return low
def check(targetMinimumDistance, rocks, n):
count = 0
curPosition = 0
j = 0
while j < len(rocks) and count <= n:
betweenDistance = rocks[j] - curPosition
if betweenDistance < targetMinimumDistance:
count += 1
else:
curPosition = rocks[j]
j += 1
if j == len(rocks) and count <= n:
return True
else:
return False