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

징검다리

1. 문제유형

• 이분탐색

2. 자료구조

• distance (int): 목적지 거리
• rocks (list): 바위 위치를 저장한 리스트
• left, right (int): 바위별 거리의 최소값, 최대값
• mid (int): 정답으로 지정한 바위별거리. left, right의 중간값
• current (int): 현재 바위 위치
• diff (int): 현재 바위 위치를 기준으로 다음 바위까지의 거리
• cnt (int): 제거한 바위 수

3. 해결과정

• 최대 범위가 10억이므로 이분탐색을 위해 rocks를 정렬 후 시작한다.

1. 이분탐색을 지정하기 위해 최소, 최대거리를 지정한 후 mid를 계산한다.
2. mid가 정답이이라고 가정한 뒤, 제거한 바위 수가 n과 같은지 판단한다.
3. 바위를 하나씩 꺼내가며 diff를 계산하고, diff가 mid보다 작으면 cnt를 증가시킨다.
4. diff가 mid보다 크면 현재 바위를 rock으로 변경한다.
5. mid를 기준으로 계산한 cnt값이 n보다 크다면, 제거할 바위를 감소시켜야 하므로 right = mid-1
6. cnt값이 n보다 작거나 같다면, 바위를 더 줄여야 하므로 left = mid+1, answer = mid
7. 1-6 과정을 left <= right일 동안 반복한다.

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

    while left <= right:
        mid = (left+right)//2
        current, cnt = 0,0

        for rock in rocks:
            diff = rock - current
            if diff < mid:
                cnt += 1
            else:
                current=rock

        if cnt > n:
            right = mid-1
        else:
            left = mid+1
            answer = mid

    return answer