[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )
왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다.
우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다.
제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다.
처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다.
그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. 예를 들어 최솟값이 5라고 가정한다. 처음 0에서 25까지 중에서 [2,11,14,17,21] 을 순서대로 추가하면서 거리가 5보다 크다면 제거해본다.
| 0 | 11 | 17 | 25 |
결과적으로 최솟값을 5로 잡는다면 우리가 제거해야 할 돌 n은 3개가 된다.
그럼 이번에는 최솟값을 4로 잡아본다. 그리고 거리가 4보다 크다면 제거한다.
| 0 | 11 | 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