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

🗂️ 문제

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

프로그래머스

 

💡 접근법

바위 사이의 거리의 최솟값을 기준으로 이진 탐색의 범위를 조절해야 한다. low는 distance의 바위 사이 거리의 최솟값인 1로, high는 바위 사이 거리의 최댓값인 distance로 설정한다. mid를 바위 사이 거리의 최솟값으로 생각하고 탐색을 진행한다.

 

이때 바위 사이의 거리의 최솟값 중 최댓값을 구하는 것이 목표이다. 따라서 바위 사이의 거리를 구하고, 구한 거리가 mid보다 작을 경우 현재 바위를 삭제한다. 만약 바위 사이의 거리가 mid보다 클 경우엔 다음 바위 사이의 거리를 구하기 위해 prev_rock에 현재 rock을 할당한다.

 

만약 삭제한 바위의 수가 n보다 클 경우에는 더 이상 탐색을 진행하면 안된다. 따라서 break를 통해 바위 사이의 거리를 구하는 과정을 멈추고, 커트라인이 너무 높아서 바위가 n보다 많이 삭제된 것이므로 커트라인을 낮추기 위해 high = mid - 1로 변경한다.

 

만약 삭제한 바위의 수가 n보다 작거나 같다면 커트라인은 적절하므로 answer에 저장해 둔다. 하지만 최댓값을 구해야하므로 커트라인을 조금 더 높이기 위해 low = mid + 1로 설정한다.

 

while() 루프가 종료된 이후, 최종적으로 저장해둔 answer를 출력한다.

 

👀 배운 코드

def solution(distance, rocks, n):
    answer = 0
    
    rocks.sort()
    rocks.append(distance)
    
    low = 1
    high = distance
    while (low <= high):
        mid = (low + high) // 2
        
        delete = 0  # 삭제한 바위 수
        prev_rock = 0  # 이전 바위 위치
        
        for rock in rocks:
            if rock - prev_rock < mid:  # 거리가 커트라인보다 작으면 바위 삭제 (왜냐면 최댓값을 구하는게 목적)
                delete += 1
            else:
                prev_rock = rock
            
            if delete > n:  # 삭제한 바위 수가 n보다 크면 break
                break
        
        if delete <= n:
            answer = mid  # 최댓값 저장
            low = mid + 1  # 최댓값을 구하기 위해 커트라인 재설정
        else:
            high = mid - 1
                
    return answer