[프로그래머스] 이분 탐색 - 징검다리

 

이 문제 또한 전과 마찬가지로 블로그를 보고 해결하였다.

문제 해결법은 전과 비슷했지만.. 해결 방법을 생각하는 것이 아직 어려운 것 같다

 

풀이방법

최소거리를 찾고, 그 최소 거리보다 작은 바위들을 제거한다.

제거된 바위 수가 n보다 크다면 거리를 좁히고, n보다 작다면 거리를 늘리며

최소 거리 중 최대 거리를 찾는다.

 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
    Arrays.sort(rocks);

    int answer = 1;
    int start = 1;
    int end = distance;
    
    while (start <= end) {
      int mid = (start + end) / 2;
      
      int cnt = 0;
      int last = 0;
      for (int i = 0; i < rocks.length + 1; i++) {
        int gap = i != rocks.length ? rocks[i] - last : distance - rocks[i-1];
        if (gap < mid) {
          cnt++;
        } else if(i != rocks.length) {
          last = rocks[i];
        }
      }
      
      if (cnt > n) {
        end = mid - 1;
      } else {
        start = mid + 1;
        answer = mid;
      }
    }
    
    return answer;
    }
}