마굿간 문제(결정 알고리즘)

import java.util.Arrays;

// 마굿간 n개 중 c마리의 말을 넣을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
public class 마구간 {
    public int count(int[] arr, int dist) { // 가장 가까운 거리를 dest로 했을 때 말을 몇마리 배치할 수 있는지 센다.
        int cnt = 1;
        int ep = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - ep >= dist) {
                cnt++;
                ep = arr[i];
            }
        }
        return cnt;
    }

    public int solution(int n, int c, int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        int lt = 1; // lt를 1로 하는 이유는 dest를 작은 수부터 검사하기 위함이다.
        int rt = arr[n - 1];
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if (count(arr, mid) >= c) {
                answer = mid;
                lt = mid + 1;
            } else rt = mid - 1;
        }
        return answer;
    }
}
iamRecoder / coding-test-training

마굿간 문제(결정 알고리즘) #1
