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

💡 Idea

완전탐색은 불가능한 크기이다 => 이분탐색

💬 사고 과정

distance가 1 이상 1,000,000,000 이하 => 완전탐색 불가능

start: 가능한 거리의 최소값 (0으로 설정)
end: 가능한 거리의 최대값 (distance로 설정)

💻 CODE

참고한 코드

def solution(distance, rocks, n):
    answer = 0
    start, end = 0, distance
    
    rocks.sort() # 정렬되어 있지 않은 상태이기 때문에 정렬해야한다.
    
    #이분 탐색
    while start <= end: 
        mid = (start + end) // 2   # 중간값
        del_stones = 0      # 제거한 돌을 카운트
        pre_stone = 0        # 기준이되는 돌(시작지점)
        
        # 바위 사이의 거리 확인
        for rock in rocks:   # 징검다리 돌면서 
            if rock - pre_stone <  mid: # 돌 사이의 거리가 가정한 값보다 작으면 제거
                del_stones += 1 
            else:         # 아니라면 그 돌을 새로운 기준으로 세운다.
                pre_stone = rock
             
            if del_stones > n:  # 제거된 돌이 문제 조건 보다 크면 for문을 나온다
            	break
                
        if del_stones > n: # 제거된 돌이 너무 많으면 가정한 값이 큰 것이므로 범위를 작은 쪽으로 줄인다.
            end = mid - 1
        else:        # 반대라면 큰 쪽으로 줄인다.
            answer = mid
            start = mid + 1
            
    return answer