징검다리

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

Explanation

This was my first attempt at binary search on a question that is not as simple as finding a value in a sorted list.

Binary search is basically guessing the answer value by putting your guess as mid. There are 2 points you need to know. After sorting, we append the distance value, which is the final end because we are gonna calculate if we can reach that end from our previous prev_rock position.

Now we have guessed the minimum distance between rocks. Logically, if we encounter a rock (current_rock) where the distance between current_rock and prev_rock is less than what we have guessed for the minimum distance between rocks, that logically doesn’t make sense. Because that means our guess is invalid as there is a distance less than our guess. So we remove our current_rock so that hopefully the next rock will have a greater distance from our prev_rock. But if distance between cur_rock and prev_rock is greater, that is perfectly fine but we just need to set prev_rock as the current rock.

The second point that is really important is that notice I returned start -1, not just start. start is the bare minimum value among the distances between stones when n stones are removed.

In the stone example, we return start - 1 because start represents the smallest distance that allows removing n rocks, so the maximum value for the minimum distance would be start - 1.

def solution(distance, rocks, n):
    start=1
    end= distance
    rocks.sort()
    rocks.append(distance)
  
    while start<=end:
        mid = (end+start)//2
        count=0
        prev_rock=0
        for rock in rocks:
            if rock-prev_rock >=mid:
                prev_rock=rock
            else:
                count+=1
        if count>n:
            end=mid-1
        else:
            start=mid+1
  return start-1