[programmers] Level4. 징검다리

풀이

• 바위 사이의 거리를 이분탐색으로 찾는 문제

• 변수의 의미 파악이 중요함.

• left, right의 평균 distance를 구함 -> 결과를 보고 distance +1 이나 distance - 1을 left 혹은 right에 할당함 -> search 영역이 반으로 줄어듬.

  def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    rocks.append(distance)
    left, right = 0, distance
  
    while left <= right:
        prev_rock = 0
        rock_count = 0
  
        # 바위 사이의 거리를 distance 변수에 저장
        # 처음에는 전체 길이의 반으로 시작함.
        # 바위 사이의 거리가 distance보다 작음 -> 제거할 바위 개수로 count함
        distance = (left + right)//2
  
        for current_rock in rocks:
            # 이전 바위 + distance 안에 현재 바위가 있으면 count 증가
            if current_rock  <  prev_rock + distance:
                rock_count += 1
  
            # 이전 바위 위치를 현재 바위 위치로 업데이트
            else:
                prev_rock = current_rock
  
        # 너무 많은 바위가 distance 안에 있음 -> distance 값 낮추기 위해 right 감소
        # right에 distance - 1해줌으로써 search 영역이 반으로 줄어듬.
        if rock_count > n:
            right  = distance - 1
  
        # 이번에는 distance가 짧기 때문에 left를 1 증가
        # left에 distance + 1 해줌으로써 search 영역이 반으로 줄어듬. 
        else:
            left  = distance + 1
            answer = distance
  
    return answer