• 오늘의 계획
    • 프로그래머스/백준 사이트에서 알고리즘 문제 풀이(이분 탐색)

  • 오늘의 회고

    • 이분 탐색 문제 풀이 : 징검다리(프로그래머스 LEVEL 4) image
      • 처음에 정렬한 다음 각 거리 별로 비교하려고 하였는데 이분 탐색 방법으로 변경하였다.
      • left, mid, right로 나누어 mid가 바위 사이의 거리보다 큰 경우에만 count값을 증가시켜 count값이 n보다 작거나 같다면(문제 조건에서는 n이지만 n으로 제출했을 때 통과가 안돼서 찾아보니 이하로 하면 된다고 했다.) 우측에서 찾아야 하므로 left를 mid + 1로 변경하고 answer와 mid 중 큰 값으로 answer로 설정하였다.
      • count값이 n보다 크다면 좌측에서 찾아야 하므로 right를 mid - 1로 변경한다.

    • 코드 :

        ```python
  def solution(distance, rocks, n):
      answer = 0
      rocks.sort()
      left = 1
      right = distance
      mid = 0

      while left <= right:
          mid = (left + right) // 2
          prev = 0
          count = 0

          for rock in rocks:
              if mid > rock - prev:
                  count += 1
              else:
                  prev = rock

          if distance - prev < mid:
              count += 1

          if count <= n:
              left = mid + 1
              answer = max(answer, mid)
          else:
              right = mid - 1

      return answer
  ```