[파이썬] [이진탐색] Pro 징검다리

문제

https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3 

코딩테스트 연습 - 징검다리

 

코드

def solution(distance, rocks, n):
    start,end=0,distance
    answer=0

    rocks.sort()

    while start<=end:
        mid=(start+end)//2
        del_stone = 0
        pre_stone = 0

        for rock in rocks:
            if rock-pre_stone < mid:
                del_stone+=1
            else:
                pre_stone=rock

        if del_stone<=n:
            answer=mid
            start=mid+1
        else:
            end=mid-1
    return answer

def solution(distance, rocks, n):
    start=0
    end=distance
    
    # 마지막과 마지막 이전까지의 거리도 구해야 하므로
    rocks.append(distance)
    rocks.sort()
    while start<=end:
        mid=(start+end)//2
        count=0
        pre_stone=0
        for rock in rocks:
            # 중앙값보다 두개의 돌 사이가 더 작으면 삭제
            if rock-pre_stone<mid:
                count+=1
            # 더 큰 경우는 이전 돌을 현재 돌 위치로 갱신
            else:
                pre_stone=rock
        
        # n보다 삭제한 돌이 작은 경우, 거리를 더 늘려 주어야 하므로 start 증가
        if count<=n:
            start=mid+1
            answer=mid
        else:
            end=mid-1
    
    return answer

생각 정리

둘 사이의 거리를 기준으로 작으면 제거하고 크면 두는 방식을 사용했다.