프로그래머스 Level4 "징검다리"

문제

프로그래머스 '징검다리'

풀이

주어지는 distance의 범위가 1 ~ 1,000,000,000인걸 확인하고 이분탐색을 써야될거라고 알긴 했지만,
이분탐색의 기준을 잡는데 한 세월 걸린 문제. (과연 level4....)

이 문제에서 mid값은 돌 사이 거리간 최소값중 최대값이 되어야한다.

각 반복마다 각각의 돌 사이의 거리들 중 mid값 보다 작을경우 해당 돌을 제거한다.
만약 제거한 돌이 문제에서 제시한 제거해야할 돌 n보다 많은 경우 start값을 올려 범위를 상향조정하고,
반대엔 경우 end를 내려 하향조정하며 이분 탐색을 진행하면 된다.

이분 탐색 문제들을 풀며 느낀 점은 이분 탐색을 진행하는 데 있어서 기준점만 알면 코드 작성하는 건 금방인데, 그 기준점을 찾는데에 시간을 너무 오래 잡아먹는다....
이분 탐색 문제들 풀면서 익숙해질 필요가 있는 듯 싶다.

Python 코드

def solution(distance, rocks, n):
  answer = 0
  # 시작지점은 0, end값은 도착지점으로 설정
  start, end = 0, distance

  # 각 돌 사이 거리를 재기 위한 정렬
  rocks.sort()

  # 이분 탐색 진행
  while start <= end:
    mid = (start+end) // 2
    
    # 앞에 있는 돌
    tmp = 0
    # 제거한 돌
    count = 0

    for x in rocks:
      # 돌 사이의 거리가 mid값보다 적을경우 제거
      if x - tmp < mid:
        count += 1

      # 반대일 경우 x(현재시점에서 비교하는 돌)을 tmp(기준이 되는 돌)로 설정
      else:
        tmp = x
    
    # 제거된 돌이 n보다 많으면 범위를 하향조정 한다
    if count > n:
      end = mid-1
    # 반대일 경우 범위를 상향조정한다.
    else:
      answer = mid
      start  = mid + 1

  return answer