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

프로그래머스

이번 문제에서 기준은 n개의 돌을 징검다리에서 제거했을 때 최소 거리이다. 먼저 범위를 생각해보면 최소값은 징검다리에 돌이 겹쳐있는 경우는 없기 때문에 1이다. 최대 값은 시작지점과 도착지점사이의 거리인 distance이다. 이 값을 기준으로 중간값(mid)가 n개의 돌을 제거했을 때 돌 사이의 거리중 최소값이라고 가정해보자.

 

이 가정하에 돌을 제거했을 때 이 값(mid)보다 작은 거리는 없어야 한다.

즉 돌 사이의 거리를 구했을 때 이 mid 값보다 작으면 제거하고 크면 두는 방식의 전략을 사용해야한다.

돌 사이의 거리를 모두 재는 것은 무의미하므로 시작지점(1)으로부터 mid값 보다 먼 거리에 있는 돌을 찾기 전까지 돌을 제거하고 찾으면 그 돌을 새로운 기준으로 삼아 다시 돌 사이의 거리를 측정하면 된다.

def solution(distance, rocks, n):
    rocks.sort()
    
    s = 1
    e = distance
    result = -1
    
    while s <= e:
        mid = (s + e)//2 #거리 길이의 최소값
        pre_stone = 0
        count = 0
        for i in range(len(rocks)):
            if mid > rocks[i] - pre_stone :
                count += 1
            else:
                pre_stone = rocks[i]
        
        if count > n:
            e = mid -1
        else:
            s = mid +1
            result = mid
    
    return result