프로그래머스: 징검다리

개인적으론 매우 어려웠던 문제이다.

Binary Search를 이용하라는 힌트가 있음에도 풀지 못하였다.

처음 떠올렸던 방식은 O(N**2)이었는데 N이 너무 커서 안될것 같았다.

이래저래 Binary Search를 적용할 방안을 떠올려보았지만, 끝까지 생각이 나지 않아 구글링을 해따...

 

아이디어는 매우 간단하다.

--> 돌 사이의 간격에 대해 binary search를 하면된다.

효율성은 O(log(D)*N)이므로 최선의 알고리즘이다.

def solution(distance, rocks, n):
    answer = -1
    rocks.sort()
    rocks.append(distance)
    l, r = 0, distance
    while l <= r:
        mid = (l + r) // 2
        num_removed = 0
        prev = 0
        for rock in rocks:
            dist = rock - prev
            if dist >= mid:
                prev = rock
            else:
                num_removed += 1
        if num_removed <= n:
            answer = max(answer, mid)
            l = mid + 1
        else:
            r = mid - 1
    return answer