결정 알고리즘, 이분탐색_마구간 배치하기

✅ 마구간에 말들을 배치할 때, 가장 가까운 말의 최대 거리를 구하세요.

마구간이 주어집니다. 마구간은 좌표위에 있습니다. 1 2 8 4 9
말을 c마리를 마구간에 배치할 때 가장 가까운 두 말 사이의 거리가 최대가 되도록 하세요
가장 가까운 두 말 사이의 거리가 최대가 될 때 그 거리를 출력하세요

package com.example.ct_inflean_2024.String;

import java.util.*;

class Main {
    //⭐️ 이분탐색
    public int count( int mid, int[] input){ //유효성 검사 함수
        int cnt=1; //맨 처음에 한 마리 배치하고 시작
        int ep= input[0];
        for(int i=1; i<input.length; i++){
            if((input[i]- ep)>=mid){
                cnt++;
                ep= input[i];
            }
        }
        return cnt;
    }

    //⭐️ 결정 알고리즘, 이분탐색
    public int solution(int n, int c, int[] input){
        int answer=0;
        Arrays.sort(input);
        //binary search
        int min= 1; //두 말이 가질 수 있는 최소 거리
        int max= input[n-1]; //두 말이 가질 수 있는 최대 거리
        while(min<=max){
            int mid= (min+max)/2;
            if(count(mid, input)>= c){ //mid값이 유효함
                answer= mid;
                min= mid+1;
            }else{
                max= 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[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
        System.out.print(T.solution(n, c, input));
    }
}
//⭐️input:
5 3
1 2 8 4 9
//⭐️output:
3

🔵 ThingsILearned

✔️ 결정 알고리즘, 이분탐색

• 결정 알고리즘은 가능한 값이 있을법한 범위를 구해서 그 안을 탐색하는 것
• 따라서 우리가 구하고자 하는 값은 말 사이 거리니까 그 거리가 있을법한 범위를 구하자면
  • min: 1
  • max: 배열 최댓값
• 따라서 마구간 배열(1 2 8 4 9)을 탐색하는게 아니라 ❌
• 거리 범위 min ~ max 사이를 탐색해야 한다 ⭕️

✔️ 유효성 검사 count 함수

• solution함수에서 결정 알고리즘, 이분탐색을 하면서 mid값을 구했음
• 이 mid값이 유효한지, 말 사이 거리로 유효한지 확인하는 작업을 count 함수에서 실행
• 말 사이 거리가 mid값보다 크거나 같은게 말 개수 c만큼 있어야 함
• 우선 말 한마리를 맨 처음에 놓고
  • 그래서 cnt가 1에서 시작
  • 그리고 for문은 1부터 돌기 시작
• ep(endpoint)라는 변수를 만들어서 input[i]에서부터 ep까지의 거리를 구했을 때 mid보다 크거나 같아야 함
  • 만약 크거나 같다면, cnt++
  • 그리고 ep를 input[i]값으로 만듦.
• 그리고 또 새로운 input[i]값에서 ep를 빼서 거리를 구하고, 이 거리가 mid보다 크거나 같은지 보고.

🔴 Trouble Shooting

• count 함수(input[i]- ep)>=mid mid보다 크거나 같아도 됨
• solution 함수의 결정 알고리즘에서 count(mid, input)>= c c보다 크거나 같아도 됨