[프로그래머스][Python] 징검다리

문제를 정리해보자.

 

1. n개의 바위를 제거한다.

2. 출발지점, 도착지점, 바위 간의 거리를 구한다.

3. 거리의 최솟값을 구한다.

 

n개의 바위를 제거하는 경우의 수만큼 최솟값이 여러 개 나온다.

그중에 최댓값이 정답이다.

 

 

풀이를 생각해보자.

 

문제에 나와 있는 예를 보자.

 

출발지점 : 0, 바위지점 : [2, 11, 14 , 17, 21], 도착지점 : 25

=> [0, 2, 11, 14, 17, 21, 25]

 

제거해야 하는 바위 개수 : 2

 

바위는 최대 50,000개이다.

50,000 C 2로 제거할 수 있는 모든 경우의 수를 찾고, 경우마다 최솟값을 찾으려 하면 시간초과가 난다.

그렇다면 어떻게 해야 할까?

모든 경우의 수를 보지 않고, 바위를 제거하는 방법을 찾아야 한다.

 

최솟값을 지정하면 된다.

최솟값에 따라서 바위를 제거하면 된다.

 

 

 

 

만약 최솟값이 13이라면?

바위 간의 거리가 13미만이 되면 안 된다. 따라서 13미만이라면 연결된 오른쪽 바위를 제거한다.

다만, 도착지점의 경우 바위가 아니다. 따라서 왼쪽 바위를 제거한다.

 

 

 

최소를 2라고 썼지만, 다른 예를 위해 1로 잡아야 한다.

 

최솟값은 1이상 25이하로 잡아야 한다. (모든 바위가 제거되었을 때 길이가 25이기 때문이다.)

 

 

구현해보자.

 

이진탐색으로 구현했다.

 

 

def solution(distance, rocks, n):

    rocks.sort()
    rocks.append(distance)

    low = 1
    high = distance

    answer = 0

    while low <= high:
        mid = (low + high) // 2  # 최솟값

        cur_rock = 0  # 왼쪽 바위
        count = 0  # 제거된 수
        for i in range(len(rocks)):
            pre_rock = rocks[i]  # 오른쪽 바위

            if pre_rock - cur_rock < mid:  # mid보다 작을 경우 제거한다.
                count += 1

            else:
                cur_rock = pre_rock

            if n < count:
                break

        if count <= n:  # mid가 클수록 제거해야 하는 돌이 늘어난다.
            answer = mid
            low = mid + 1

        else:
            high = mid - 1

    return answer


print(solution(25, [2, 14, 11, 21, 17], 2))

 

1. count == n

개수에 맞게 제거되었다.

 

2. count < n

mid가 클수록 제거해야 하는 돌이 늘어난다.

mid를 더 크게 해준다.

 

3. count > n

mid가 작을수록 제거해야 하는 돌이 줄어든다.

mid를 작게 해준다.

 

다만, count가 n보다 작을 때가 최솟값이 될 수 있다.

예를 들어, n은 2인데 count는 1일 경우.

count가 1이라는 뜻은 1개의 거리 빼고는 다 mid이상의 거리의 길이 가지고 있다는 것이다.

따라서 1개의 바위를 제거하고 나면, 어느 바위를 제거해도 mid보다 짧은 거리가 나올 수 없다.

즉, 해당 mid에 count가 1이라서 2보다 작지만, count는 1이상 될 수 있기 때문에 최솟값이 될 수 있다.

 

 

시간 복잡도는 O(nlogn)이다.