마구간 정하기(결정 알고리즘)

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,

가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

이분검색을 이용한 결정 알고리즘으로 푸는 문제

현재 인덱스의 마구간의 위치 - 이전 마구간의 위치가 mid 값 보다 크면 가능한 경우

lt와 rt는 각각 1과 끝 마구간으로 잡고 시작한다, lt를 처음 마구간으로 잡으면 처음 값이 1이 아닌 경우 mid값을 정할때 문제가 생긴다

 

import java.util.*;

class Main {


    public int solution(int n, int m, int[] arr){
    	// lt는 1부터 시작해야 함, 배열이 1부터 시작하지 않을수도 있기때문에
        int lt = 1, rt = Arrays.stream(arr).max().getAsInt(), mid;
        int cnt = 0;
        int ans = 0;
        while(lt <= rt){
            int tmp = arr[0];
            mid = (lt+rt)/2;
            cnt = 1;
            //시작부터 진행하는게 유리하니 처음 값 부터 시작한다고 가정
            for(int i = 1; i < n; i++){
                //현재 인덱스에서 이전 인덱스 값을 뺀 값이 mid로 잡은 말 사이의 거리 값 보다 크면 가능한 경우
                if (arr[i] - tmp >= mid){
                    cnt++;
                    tmp = arr[i];
                }
            }

            //루프를 돌고 나서 tmp로 가능했을때 mid값을 증가시킨다
            if(cnt >= m){
                lt = mid+1;
                ans = mid;
            }

            else {
                rt = mid-1;
            }

        }
        return ans;
    }

    public static void main(String[] args) {
            Main t = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[] arr = new int[n];
            for(int i =0; i < n; i++) arr[i] = in.nextInt();
            Arrays.sort(arr);
            System.out.println(t.solution(n, m, arr));
    }
}