たんさくざんせき

プログラマーlev.4足場石これは探索問題です.
コアは、マットレス石の配列の過程で、私がこのマットレス石を拭いたとき、発生した距離はいくらですか?マスターする.
以前にもまとめたように,二分探索という概念自体は簡単であるが,その内部に関数が必要であり,この関数を実現するのは容易ではない.

問題を見ると、私が削除する岩の個数はnで、もし私が探求するこの距離とマット石を除去する時に発生する距離を比べて、マット石を除去する時に発生するこの距離を、もしこの探索の距離がもっと小さいならば、それは私が更にマット石を整理することを意味します.
従って、清掃マットの大きさをcountと呼ぶと、count>nは清掃が多すぎることを示すため、この探索を減らすべきであり、逆に、この探索を増やすべきである.
また、ケンブリッジを巡回して距離を探す論理も実現しなければならない.これは実現に近い.

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    rocks.insert(0, 0)
    # 먼저 0과 첫번째 징검다리와 마지막의 거리도 구해주어야 하므로 해당 로직
    
    left, right = 0, distance
    answer = -1
    
    while left <= right:
        mid = (left + right) // 2
        count = 0
        j = 0 # 비교대상 징검다리
        i = j + 1 # 내가 치워버릴수도있는 징검다리
        while i < len(rocks): # rock을 모두 순회하면서
            if rocks[i] - rocks[j] < mid: # 징검다리의 차이가 탐색중인 거리보다 작으면
                i += 1 # 징검다리를 치워버리고 거리를 벌린다.
                count += 1
                continue
                # 만약 거리가 탐색중인 거리보다 커졌으면 다음 징검다리 탐색
            j = i
            i += 1
        if count <= n: # 최대값을 찾기 위한 이분탐색 조건
            answer = max(answer, mid) # 최대값 저장
            left = mid + 1
        else:
            right = mid - 1

    return answer