프로그래머스 - 징검다리 파이썬

문제 

프로그래머스

문제 설명

 

접근

누가 봐도 이분탐색 문제이다 

 

코드 

def solution(distance, rocks, n):
    # 만약 주어진 rocks 배열의 길이가 n과 같다면, 모든 돌을 제거해야하므로 distance를 반환
    if len(rocks) == n:
        return distance

    # rocks 배열을 오름차순으로 정렬, 마지막에 distance를 추가하여 시작과 끝값을 설정
    rocks.sort()
    rocks.append(distance)
    answer = 0
    start, end = 0, distance

    while start <= end:
        # 이분 탐색의 중간값을 계산
        mid = (start + end) // 2
        prev_rock = 0
        removed_rocks = 0

        # 각 돌 사이의 거리를 비교하여 mid 값을 기준으로 돌을 제거하는 개수를 세기
        for rock in rocks:
            if rock - prev_rock < mid:
                removed_rocks += 1
            else:
                prev_rock = rock

        # 제거해야 할 돌의 개수가 n보다 크다면, mid 값을 줄이기
        if removed_rocks > n:
            end = mid - 1
        # 제거해야 할 돌의 개수가 n보다 작거나 같다면, mid 값을 늘리기
        else:
            answer = mid
            start = mid + 1

    # 최적의 인원 수를 반환
    return answer