[프로그래머스][level4] 징검다리 - python

문제 링크

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

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

 

풀이 

- 이분 탐색 문제 

최소 거리를 mid 라고 설정하고,

시작 위치에서부터 다음 바위까지 거리를 구해서 mid 보다 작다면 최소거리가 mid 가 아닌 게 되므로 바위 제거 

mid보다 크면 그 바위까지 이동하고 다음 바위까지 또 거리 비교해서 작으면 바위 제거 

 

만약 제거된 바위의 수가 n보다 많으면 최소 거리가 너무 길다는 것이므로 최소 거리 줄이기

제거된 바위의 수가 n보다 작거나 같으면 최소 거리 늘리기 

def solution(distance, rocks, n):
    answer = 0
    # 이분 탐색 시작 범위 설정 
    start = 0
    end = distance
    # 시작위치에서 바위까지 거리 오름차순 정렬 
    rocks.sort()
    # 도착 지점 추가 
    rocks.append(distance)
    
    while start <= end :
        # 최소 거리 
        mid = (start+end) // 2 
        # 제거한 바위 개수
        cnt = 0 
        # 시작 위치 
        now = 0 
        
        for i in rocks :
            # 현재 위치에서 바위까지 거리
            dist = i - now 
            # 최소거리보다 작으면 
            if dist < mid :
                # 바위 제거 
                cnt +=1 
            else :
                # 최소거리와 크거나 같으면 그 바위로 이동 
                now = i
         
        # 바위가 n보다 많이 제거됐으면 최소 거리 줄이기        
        if cnt > n :
            end = mid - 1 
        else :
        	# 최소 거리 늘리기 
            answer = mid 
            start = mid + 1 
            
    return answer