프로그래머스 - 징검다리

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 징검다리

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

풀이 : 각 지점 사이의 거리 (mid)를 기준으로 제거되는 바위의 갯수를 체크한다. 체크된 바위의 갯수가 2개가 처음 되는 지점을 이분탐색을 실시한다.

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int start = 0, end = distance;
       	Arrays.sort(rocks);
		long l = 0, r = distance;
		while(l <= r) {
			long mid = (l + r) / 2, k = 0, d = 0;
			for (int i = 0; i < rocks.length; i++) {
				if(rocks[i] - k < mid) d++;
				else k = rocks[i];
			}

			if(d > n) r = mid - 1;
			else l = mid + 1;
		}
		return (int) r;
    }
}