프로그래머스

징검다리

def solution(distance, rocks, n):
    answer = -1
    # mid(구해야 하는 값)은 돌 사이의 거리가 될 수 있는 최솟값
    # 돌들을 하나하나 비교해서 mid보다 작으면 그 돌을 제거..
    # 만약에 n보다 많이 제거하면 최솟값이 작아져야 하므로(그래야 돌을 덜 제거하니까..?) 구간을 작아지게 right = mid-1
    # n보다 작거나 같으면 구간을 작게 left = mid+1 하고 answer와 비교하여 큰 값을 answer에 저장
    left = 1
    right = distance
    rocks.sort()
    while left <= right:
        mid = (left+right) // 2
        _rocks = [0]
        _rocks.extend(rocks)
        _rocks.append(distance)
        removedRocks = 0
        prevRock = 0
        for i in range(1, len(_rocks)):
            curRock = _rocks[i]
            diff = curRock - prevRock
            if diff >= mid:
                prevRock = curRock # 비교할 전 돌을 현재 돌로 갱신
            else :
                removedRocks += 1
        if removedRocks > n:
            right = mid-1
        else:
            left = mid+1
            answer = max(answer, mid)
        # elif removedRocks < n:
        #     left = mid + 1
        # else:
        #     answer = max(answer, mid)
        #     left = mid+1
            
    return answer

• 문제에 오류가 있는지 바위를 n개 제거하는 것이 아니라 n개 '이하'를 제거하는 방식으로 풀어야 정답처리 된다.