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

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

오랜만에 이진탐색 문제를 풀었는데 어떻게 접근해야할 지 막막했다. 구하라는 거리의 최솟값을 변수로 두고 이거를 변화시키면서 탐색해보기로 했다.

def solution(distance, rocks, n):
    answer = 0
    
    rocks.append(0)
    rocks.append(distance)
    rocks.sort()
    dif = []
    
    for i in range(1, len(rocks)):
        dif.append(rocks[i] - rocks[i-1])
    
    
    # 거리의 차를 먼저 구하고 정렬시키자
    
    # 거리를 저기 뭐다냐 그 변수로 두고 거리 기준으로 배치했을 때 바위 몇 개 들어가는지? 테스트해볼까?
    start = 0
    end = distance
    
    while start < end:
        mid = (start + end) // 2
        
        result = -2
        for d in dif:
            if d >= mid:
                result += 1
        
        if result > n:
            start = mid + 1
        else:
            end = mid
            answer = mid
        
    return answer

위 코드처럼 돌 사이의 거리를 배열로 만든 다음 정렬해서 최솟값을 변화시키면서 사라지게되는 돌의 개수가 몇 개인지를 셌다. 그리고 틀렸다. 돌이 사라지게 되면 돌 사이의 거리가 변하게 되는데 그거를 반영해주지 못했다.

방법이 안 떠올라서 질문하기와 블로그를 참고했다. 거리계산하는 과정을 while문 안으로 넣었다. 오른쪽으로 탐색하면서 이전 바위와의 거리를 계산해서 mid보다 작으면 삭제하고, mid이상이면 이전 바위 변수를 업데이트 하는 방식으로 바위가 삭제되는 효과가 연산 과정에 반영이 되도록했다.

def solution(distance, rocks, n):
    answer = 0
    
    rocks.sort()
    rocks.append(distance)
    start = 1
    end = distance
    
    while start <= end:
        mid = (start + end) // 2
        
        delete = 0
        pr = 0
        for r in rocks:
            dif = r - pr
            if dif < mid:
                delete += 1
                if delete > n:
                    break
            else:
                pr = r
        
        if delete > n:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1
        
    return answer