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

https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리

 

이분탐색 문제로 mid 를 잡고 해당 mid 가 조건에 부합하는지를 판별한다.

 

아래의 c 는 제거한 바위의 수이다. mid 가 커서 반드시 제거해야 할 바위의 수가 n 보다 많아지면 mid 는 최솟값이 될 수 없으므로 보다 작은 값에서 답이 나온다. (end = mid - 1)

 

그렇지 않으면 start = mid + 1 로 설정한다. 결론적으로 구해야 할 답은 c 가 n 보다 같거나 적음을 만족하는 mid 의 최댓값(= answer) 이다. 이것을 증명하는 것은 어렵지 않다. (문제의 답은 존재하고, answer 이 문제의 답이 아니라면 c > n 이면 답이 될 수 없다는 조건과 모순이 생기기 때문이다.)

 

또한, rock 에 distance 를 넣는 이유는

예를 들어, 5 10 11 12(= distance) 라고 했을 때 mid 가 5 라면 11 을 제거 하더라도 10 과 12 의 차이가 2 < 5 이기 때문에 10 을 또 제거해야 하는 상황을 만들어 줘야 하기 때문이다. 10 보다 앞의 제거되지 않는 수가 있다면 그 수는 이미 10 과의 거리가 mid 보다 같거나 크기 때문에 distance 와의 거리는 mid 보다 크다. 그러므로 rock 에 distance 를 넣어 마지막 계산에서 c 에 1 을 더할지만을 판단하면 된다.

 

def solution(distance, rocks, n):
    answer = 0 
    start = 1
    end = distance
    mid = 0
    rocks.sort()
    rocks.append(distance) 
    
    while start <= end:
        mid = (end + start) // 2
        rock = 0
        c = 0
        
        for i in rocks:
            if i - rock < mid: 
                c += 1
            else:
                rock = i
            
            if c > n:
                break
        
        if c > n:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1
        
    return answer

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