결정 알고리즘(마구간)

27 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• 유효성 검증을 통해 증명하는 것은 어려운 것이 아니지만 검증하는 구간을 작성하는 스킬이 중요하다.

코드

import java.util.*;

class Main {
    // 배열 검증 함수
    public int count(int[] arr, int dist) {
        // 두 말의 최대 거리 1부터 시작
        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;
        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;
    }

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