프로그래머스 - 징검다리 (바위 부수기)

def solution(distance, rocks, n):
    rocks.sort()
    minDistance, maxDistance = 1, distance
    current = (minDistance + maxDistance) // 2
    
    while True :
        cnt = 0
        pre = 0
        for idx in range(len(rocks)):
            if rocks[idx] - pre < current :
                cnt += 1
                if cnt > n :
                    break
            else :
                pre = rocks[idx]
                continue


        if cnt <= n :
            minDistance = current
        else:
            maxDistance = current

        next = (minDistance + maxDistance) // 2
        if next == current :
            return current
        current = next

이진탐색에 대해서 더 많이 공부할 수 있었던 문제였다. 무엇을 이진탐색으로 찾아야하는지, 찾기 위해서는 어떤 조건이 필요한지 등을 생각해봐야했던 문제였다. 처음에 문제 보고는 도대체 이게 왜 이분탐색인가 도저히 모르겠었던 그런 문제...

구해야 하는 것 = 조건에 맞는 최대값 = 이진탐색 검색 대상

조건 : 바위 사이의 거리의 최솟값이 n (이진 탐색값) 이상
조건에 만족하는지 확인하기 위한 과정 : 이전바위와 다음바위의 거리 확인, 현재 정해진 최솟값(이진 탐색값)보다 작으면 뒷바위 부수기. 부순 갯수가 n을 넘어가면 break. 부순 갯수에 따라서 min, max, mid 값 설정