Programmers. 징검다리

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 징검다리

문제 풀이

distance의 범위가 심상치가 않다. 왠지 log n의 시간복잡도를 갖는 기법을 써야할 듯하다. 또한, 바위를 빼는 가짓수가 너무 많기 때문에 그리디나 브루트 포스로는 풀리지 않을 것 같다.

제시된 조건에서 정답이 가질 수 있는 값의 범위는 1부터 distance가 된다. 그렇다면 바위를 n개 뺐을 때 거리의 최솟값이 최대가 되는 지점을 정답이 가질 수 있는 범위 내에서 탐색하여 목표로 하는 거리를 갖기 위해 적어도 몇 개의 돌을 빼야하는 지 산출하여 기준을 잡으면 되겠다.

1회의 탐색은 바위의 개수 만큼이고 전체 탐색 횟수는 distance 기준으로 이분 탐색을 진행한다 했을 때 $log(distance)$가 된다. 그리고 n 개를 뽑았을 때 가질 수 있는 값 중 가장 큰 값이므로 Upper Bound를 구하고 그에 대해 -1하여 리턴하면 되겠다.

• rocks 배열 정렬
• 값이 주어졌을 때 해당 값보다 돌 사이의 거리가 작을 경우 빼야하는 돌로 간주하며 적어도 빼야하는 돌의 개수를 리턴하는 함수를 작성한다.
• 좌, 우측의 값을 1, distance로 두고 mid 값 설정한 뒤 mid 거리를 얻기 위해 적어도 빼야하는 돌의 개수를 이전에 정의했던 함수로 구한다.
• 구한 값이 n보다 크면 거리가 너무 크다는 것을 의미하므로 우측 값을 mid로 교체한다.
• 구한 값이 n보다 작거나 같으면 적어도 더 큰 값을 갖는지 체크를 위해 좌측 값을 mid + 1로 교체한다.
• Upper Bound에 따라 n + 1을 갖는 값 중 최솟값이 결과값이 되므로 1을 빼서 리턴하면 된다.

python 코드

def solution(distance, rocks, n):
    rocks.sort()
    def count(val):
        cnt = 0
        dist = 0
        for i in range(len(rocks)):
            if i == 0:
                if rocks[i] < val:
                    cnt += 1
                    dist = rocks[i]
                continue
            if dist + rocks[i] - rocks[i - 1] < val:
                cnt += 1
                dist += rocks[i] - rocks[i - 1]
            elif dist + rocks[i] - rocks[i - 1] >= val:
                dist = 0
        return cnt

    l, r = 1, distance
    while l < r:
        mid = l + (r - l) // 2
        s = count(mid)
        if s > n:
            r = mid
        elif s <= n:
            l = mid + 1
    return r - 1