[인프런] 06-10 마구간 정하기 (결정알고리즘)

📖  문제

---

• 첫 줄에 자연수 N(3 <=N <=200,000)과 C(2 <=C <=N)이 공백을 사이에 두고 주어집니다.
• 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
  • N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며,
    마구 간간에 좌표가 중복되는 일은 없습니다. 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
  • C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최댓값을 출력하는 프로그램을 작성하세요.
  • 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,

출력 예시

 

⚠️  주의사항

---

• 입력 된 값이 정렬되지 않은 배열 일 수도 있다.
• 이분 검색을 활용 할 것

 

✍️  이해

---

 

/**
 * 1. N 과 C 입력, N개로 이루어진 배열 arr
 * 2. 이분검색 하던대로 while문까지 생성
 *  2-1. arr을 sort해주고 lt는 1부터 시작
 * 3. cnt = 1 초기화후 arr의 크기 만큼 반복, temp = arr[0]; 말 배치
 *  3-1. 말이 배치 될 수 있는 곳인지 확인 할 것
 *  3-2. arr[i] - temp >= mid -> cnt증가, temp를 arr[i]로 초기화
 *  3-3. return cnt;
 * 4. if cnt 값이 말의 수 보다 크거나 같으면 cnt 증가, mid 기준 왼쪽 값 볼 필요 없어짐 -> lt = mid + 1;
 * 5. else -> 오른쪽 값 볼 필요 없으므로 rt = mid - 1;
 * 6. return answer;
 */

 

✏️  풀이

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public int count(int[] arr, int mid) {
        int cnt = 1;
        int temp = arr[0];

        for (int i = 1; i < arr.length; i++) {

            if(arr[i] - temp >= mid ) {
                cnt++;
                temp = 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 T = new Main();

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(T.solution(N, C, arr));

    }
}

---