이진탐색 연습 - 징검다리(프로그래머스)

이진탐색을 연습하는 중이라서, 바로 직전에 프린터 문제를 풀었더니 프린터 풀이 방식과 동일한 방식으로 풀게 되었다.

살짝 변화를 준 부분은, mid의 변화에 따라 [가장 인접한 바위의 최대거리] 값이 주어질 때,

그 상황에서 바위는 몇 개까지 둘 수 있는지를 세보는 함수(isOK로 명명)가 boolean 을 return 하도록 해본 점이다.

(직전에 풀었던 공유기에서는 거의 유사한 함수였지만 카운트한 int값을 반환해주었다.)

남겨두어야 하는 바위의 개수보다 적은 경우에는 False, 남겨두어야 하는 바위 이상인 경우에는 True를 주어서

본함수(?)에서 불리안 값을 참고해서 mid를 늘려도 될지, 아니면 mid를 더 줄여야 할지 판단하도록 했다.

 

 

1. 손정리

2. 코드

def solution(distance, rocks, n):
    # rocks 를 오름차순으로 정렬
    rocks.sort()

    # 가장 인접한 바위 사이의 거리가 주어졌을 때, 남겨두어야 하는 바위의 개수 이상으로 남길 수 있는지 판단해주는 함수
    def isOK(min_dis):
        nonlocal n
        nonlocal rocks
        prev = 0
        count = 0
        for i in range(0, len(rocks)):
            cur = rocks[i]
            dis = cur - prev
            if dis < min_dis:
                continue
            else:
                count += 1
                prev = cur

        if count >= len(rocks) - n:
            return True
        else:
            return False

    # 가장 인접한 바위 간의 거리로 가능한 범위를 정해두고
    # mid 조정해가는 이분탐색 진행
    start = 1
    end = distance
    answer = 0

    while start <= end:
        mid = (start+end)//2
        if isOK(mid) is True:
            answer = max(answer, mid)
            start = mid + 1
        else:
            end = mid - 1

    return answer