[프로그래머스/Python] 징검다리 - Level4

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

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

이 문제는 이분 탐색 문제였다. 이분 탐색 문제는 어느 문제든 코드 구조는 정말 비슷한데 이분 탐색할 대상? 기준? 을 찾는 것이 어려운 것 같다. 여러 문제를 풀어보면서 보는 시각을 키워야 할 것 같다. 이 문제에서는 최소 거리를 이분 탐색 대상으로 삼았다. 최소 거리를 특정한 다음 바위를 제거해가면서 n과 맞는지 확인한다. n과 최소 거리가 모두 맞다면 정답을 찾은 것이다. 

def solution(distance, rocks, n):
    answer = 0
    left, right = 0, distance
    rocks.append(distance) # 마지막 도착지까지 거리를 계산하기 위해 추가
    rocks.sort() # 오름차순 정렬
    
    # 이분 탐색 수행
    while left <= right:
        mid = (left + right) // 2 # 특정한 최소거리
        current, remove =  0, 0 # 현재 위치, 제거할 바위 수
        min_distance = float('inf') # mid에서 최소 거리
        
        # 거리 구하기
        for rock in rocks:
            dis = rock - current
            if dis < mid: # mid 보다 작으면 바위 제거
                remove += 1
            else: # mid 보다 작지 않다면 현재 위치 옮기고 mi에서 최소 거리 계산
                current = rock
                min_distance = min(min_distance, dis)
                
        if remove > n: # n보다 많다면 mid를 줄임
            right = mid - 1
        else: # n보다 많지 않다면 최소 거리를 answer에 저장하고 mid를 늘림
            answer = min_distance
            left = mid + 1
        
    return answer

1. left, right 초기화 후 rocks에 도착 지점을 추가하고 오름차순으로 정렬한다.

2. 최소 거리를 기준으로 이분 탐색을 수행한다.

    2-1. mid, current, remove, mid_distance 를 초기화한다.

3. 바위와 현재 위치 사이의 거리(dis) 를 구한다.

    3-1. dis < mid 라면 바위를 제거한다.

    3-2. dis >= mid 라면 현재위치(current) 를 바위위치(rock) 으로 옮기고 최소 거리를 계산하여 min_distance에 저장한다.

4. mid 를 다시 설정한다.

    4-1. 제거한 바위 수(remove) 가 n보다 많다면 현재 탐색한 구간보다 아래쪽에서 탐색한다.

    4-2. 제거한 바위 수(remove) 가 n보다 많지 않다면 현재 탐색한 구간보다 위쪽에서 탐색한다. answer에 최소 거리를 저장한다.