설명

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

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

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

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

코드

public class Stall {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }
        int solution = solution2(input1, input2, arr);
        System.out.println(solution);
    }
    public static int solution(int m, int k, int[] arr){
        int answer = 0;

        Arrays.sort(arr);   //배열을 우선 정렬
        int max = Arrays.stream(arr).max().getAsInt();  //최댓값
        int min = Arrays.stream(arr).min().getAsInt();  //최솟값

        //마구간의 거리는 최소 0 ~ 최대 max-min 의 거리를 가짐
        int lt = 0;
        int rt = max-min;
        //lt값이 결국 rt보다 커지면 while 종료
        while(lt<=rt){
            int mid = (lt+rt)/2;
            int cnt = count(mid, arr);
            if(cnt>=k){
                lt = mid+1;
                answer = Math.max(answer, mid);
            }else{
                rt = mid-1;
            }
        }

        return answer;
    }
    public static int count(int mid, int[] arr){
        int count = 1;

        //배열에서 mid의 크기만큼 거리에 마구간의 경우 몇개의 말을 넣을 수 있는지 확인
        int stall = arr[0];
        //0번 마구간에는 무조건 말이 들어간다
        for(int i=1; i<arr.length; i++){
            if(arr[i]-stall>=mid){
                count++;
                stall = arr[i];
            }
        }
        return count;
    }

    public static int solution2(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(count2(arr,mid)>=c){
                answer = mid;
                lt=mid+1;
            }else rt=mid-1;
        }
        return answer;
    }
    //결정 알고리즘에서 count2 메서드를 구현하는게 능력이고 가장 중요한 부분
    public static int count2(int[] arr, int mid){
        int cnt = 1;
        int ep = arr[0];
        for(int i=1; i<arr.length; i++){
            if(arr[i]-ep >= mid){
                ep = arr[i];
                cnt++;
            }
        }
        return cnt;
    }
}

위 코드에서 solution과 count가 내가 풀이한 방법이고 solution2와 count2가 강사님의 코드이다. 두 코드를 보면 많은 차이점은 없고 시작 기준과 종료 기준의 차이 정도이다. 그리고 저번 시간에 학습했던 내용이라 똑같이 풀이하면 된다는 생각으로 풀어서 그런지 좀 쉬웠다.

결정 알고리즘 문제를 풀면서 내가 생각했던 부분은

1. lt와 rt를 정할 정답을 위한 수들의 범위
2. count() 메서드를 통해 값을 구분하고 조건에 따라 lt와 rt의 값의 증가와 감소
3. count() 메서드 내부의 동작 구조

였다. 그리고 강사님께서도 강의 중 결정 알고리즘의 가장 중요한 부분은 count() 메서드를 구현하는 능력이라고 하셨다. 뮤직비디오 문제를 풀어냈다면 이번 마구간 문제도 쉽게 풀어낼 수 있을거다.

오늘은 쉽게 풀었지만 비슷한 유형의 문제가 또 나온다면 바로 풀어내긴 어려울거 같다. 계속 연습을 해두어서 다음에 바로 풀어낼 수 있는 능력을 길러내보자.

결정 알고리즘에서 가장 중요한 부분은 count() 메서드를 구현해내는 능력이다. 그리고 이진 검색의 구현부분은 외워둔것 처럼 적어낼 수 있어야한다.