[프로그래머스] 이분탐색 - 징검다리 (파이썬)

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43236

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

 

나의 풀이

이전에 풀었던 입국심사 와 비슷한 문제다. 이분탐색의 개념을 확실히하고, 이 문제의 유형은 확실하게 풀고 넘어갈 수 있도록 해야겠다 ㅠㅠ 

def solution(distance, rocks, n):
    answer = 0
    left = 0
    right = distance
    rocks.sort()

    # left, right, mid는 거리
    while left <= right:
        mid = (left + right) // 2
        remove_rock = 0
        prev_rock = 0
        min_a = 1000000001

        for rock in rocks:
            # 만약 현재 돌과, prev돌의 거리가 mid보다 작으면, 시작점을 mid로 옮겨줘야하니까 삭제하게되겟지? 
            if rock - prev_rock < mid:
                remove_rock += 1
            # 그게 아니라면, rock-prev_rock 값이 min이 되는 값을 answer에 저장하고 prev를 rock위치로 옮김 (다음 rock 검토)
            else:
                min_a = min(min_a, rock-prev_rock)
                prev_rock = rock

        # 삭제한돌이 n보다 많으면 거리를 줄여줘야하는 것이므로 right를 mid-11 값으로 변환하고 다시 ㄱ
        if remove_rock > n:
            right = mid-1
        else:
            answer = min_a
            left = mid+1
    return answer