[알고리즘] 문제10.마구간 정하기(결정알고리즘)

 

 

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

 

설명

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

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

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

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

입력

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.

둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

출력

첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

예시 입력 1 

5 3
1 2 8 4 9

예시 출력 1

3

 

 

 

 

풀이전략

1. 이진탐색 이용

최소거리가 가능한 범위를 정하고 이진탐색으로 그 범위를 빠르게 좁혀나감.

(최소값: 인접한 두 마구간의 최소거리 / 최대값: 가장 먼 두 마구간의 거리)

배치가능한 말의수가 배치해야할 말의 수보다 많다면 lt = mid +1로 높임 (가장 인접한 말의 최대거리를 구하는 것이므로 )

반대로 적다면 rt = mid -1로 낮춤

 

lt와 rt를 이용한 결정 알고리즘 패턴을 외워두자

 

2. 배치가능한 말의 수를 세는 메서드 생성

마구간의 위치, 최소거리가 주어졌을 때 배치가능한 말의 수를 세는 메서드 생성

 

 

 

코드

//최소거리가 주어졌을때 몇마리 배치가능한지 세주는 메서드
public static int count(int[] arr, int dist){
    int count=1;
    int ep=arr[0];

    for(int i=1; i<arr.length; i++){
        if( (arr[i]-ep) >= dist ){
            count++;
            ep=arr[i];
        }
    }
    return count;
}

public static void main(String[] args){

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] arr = new int[n];
    int answer = 0;

    for(int i=0; i<n; i++) arr[i]=sc.nextInt();

    Arrays.sort(arr);

    int lt=Integer.MAX_VALUE, rt=arr[arr.length-1] - arr[0];

    for(int i=0; i<n-1; i++){
        int num = arr[i];
        int nextNum = arr[i+1];
        if(nextNum-num<lt) lt=nextNum-num;
    }


    while(lt<=rt){
        int mid = (lt+rt)/2;
        if(count(arr,mid) >= m){ 배치가능한 말의 수가 배치해될 말의 수 보다 많다면 거리 증가
            answer = mid;
            lt = mid+1;
        } else{
            rt = mid-1;
        }
    }

     System.out.print(answer);
}