[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다.

우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다. 
제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다.

처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다. 

그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. 예를 들어 최솟값이 5라고 가정한다. 처음 0에서 25까지 중에서 [2,11,14,17,21] 을 순서대로 추가하면서 거리가 5보다 크다면 제거해본다.

0

2

11

14

17

21

25

 결과적으로 최솟값을 5로 잡는다면 우리가 제거해야 할 돌 n은 3개가 된다.

 

그럼 이번에는 최솟값을 4로 잡아본다. 그리고 거리가 4보다 크다면 제거한다.

0

2

11

14

17

21

25

결과적으로 최솟값을 4로 잡는다면 우리가 제거해야 할 돌 n은 2개가 된다.  n은 2이기 때문에 만족한다.

 

이러한 방식으로 최솟값을 기준으로 n을 만족하는 최대 최솟값을 구할 수 있다. 
그렇다면 문제는 최솟값의 후보가 1~distance(1,000,000,000)까지라 너무 크다는 것이다. 아까 이분탐색의 냄새를 맡았다면 최솟값을 이분탐색으로 비교하면서 최대 최솟값을 구하면 된다는 생각이 떠오른다.
따라서 최솟값을 이분탐색으로 정하고, n을 만족하는 경우 더 큰 최솟값을 구해보기 위해 L = M+1로, n을 만족하지 않는 경우에는 이전보다 작은 최대 최솟값을 구하기 위해 R=M-1을 해주면 된다.

이제 코드를 작성하면 된다.

def solution(distance, rocks, n):
    rocks = sorted(rocks) # 정렬해주기
    rocks_num = len(rocks)
    L = 1
    R = distance
    final = 0
    while L<=R:
        M = int((L+R)/2) # 예상하는 최솟값
        remove = 0
        tmp_rocks = [0]
        for i in range(rocks_num):
            if (rocks[i] - tmp_rocks[-1] >= M) and (distance - rocks[i] >= M):# 다리 놓기 가능
                tmp_rocks.append(rocks[i])
            else: # 다리 못놓음
                remove += 1
        if remove <= n:
            final = M
            L = M+1
        else:
            R = M-1
    return final

 

결론 : 아 이분탐색 어렵다....거꾸로 생각해보는 습관을 들이자