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

문제를 풀어보려고 딱 링크에 들어간 순간...!!!!

가장 가까운 두 말의 거리가 최대가 되는 그 최댓값을 출력...???

독해가 안돼서 엄청나게 헤맸다.. @_@

결국 해설을 좀 보고 이해...! 개인적으로 이번 문제는 코드보다 독해가 더 어려웠다는 얘기가 ㅎㅎ

 

잡답은 멈추고 이제 전체 코드를 확인해보겠다!

 

import java.io.*;
import java.util.Arrays;

public class Unit6 {
    public static int count(int[] arr, int dist){
        int cnt=1;//최소 말 한마리를 배치
        int ep=arr[0];//제일 작은 왼쪽 좌표에 배치
        for(int i=0;i<arr.length;i++){
            if(arr[i]-ep>=dist){
                cnt++;//말의 개수를 증가
                ep=arr[i];//다음에 비교할 좌표에 넣는다
            }
        }
        return cnt;
    }
    public static int solution(int len,int num, int[] arr) {
    	 Arrays.sort(arr); //좌표를 정렬
    
        int lt=1; //말 사이의 최소 거리는 1
        int rt=arr[len-1]-arr[0]; //최댓값은 맨 처음 좌표와 맨 마지막 좌표의 차이
        int answer=0;//거리

        while(lt<=rt){
            int mid=(lt+rt)/2; //mid가 말 사이의 거리
            if(count(arr,mid)>=num){//말이 좌표에 얼마나 들어갔는지 체크
                answer=mid;
                lt=mid+1;
            }
            else rt=mid-1;
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr=br.readLine().split(" ");
        int len=Integer.parseInt(arr[0]);
        int num=Integer.parseInt(arr[1]);
        String[] str=br.readLine().split(" ");
        int[] list=new int[len];
        int j=0;
        for(String x: str){
            list[j++]=Integer.parseInt(x);
        }

        System.out.println(solution(len,num,list));
    }
}

 

코드는 이전 시간에 해결한 뮤직비디오 문제와 비슷하다. 이번에는 solution, count 함수를 나누어서 설명을 해보겠다.

우선 main 함수에서 좌표의 개수, 말의 개수, 좌표의 리스트를 입력받습니다.

 

이 변수들을 solution 함수에 넣는다. solution 함수 코드들부터 분석해보자.

 

public static int solution(int len,int num, int[] arr) {
		 Arrays.sort(arr);

        int lt=1;
        int rt=arr[len-1]-arr[0];
        int answer=0;//거리

        while(lt<=rt){
            int mid=(lt+rt)/2;
            if(count(arr,mid)>=num){
                answer=mid;
                lt=mid+1;
            }
            else rt=mid-1;
        }
        return answer;
    }

 

(list들은 정렬이 안되고 제공될 수 있으므로 정렬!!)

 

우선 lt와 rt의 값을 정한다. lt와 rt는 말들 사이의 거리다.

 

lt는 말들 사이의 최소 거리 값을 넣으면 된다. 최소 거리는 당연히 1이다.

rt는 말들 사이의 최대 거리 값이다. 최대 거리는 정렬된 좌표 배열의 최댓값과 최솟값의 차이다.

 

mid는 더 조건에 맞는 답을 찾아가기 위해 이분 검색을 위한 변수(말들 간 거리)다.

count 메서드의 리턴 값은 말이 들어갈 수 있는 좌표의 개수다.

 

예시를 보면 

 

1 2 4 8 9 좌표 배열이 있다. 여기서 mid(말 사이의 거리)가 1이라면 모든 좌표에 말이 들어갈 수 있다.

즉 이러면 count 메서드의 리턴 값이 5이다. 리턴 값은 다시 말하지만 말이 들어갈 수 있는 좌표다.

 

이는 1 2 8. 1 2 9. 1 4 8. 이 모두 가능하므로 예시 1의 조건인 말의 개수 3을 충족시키므로 if문을 통과한다.

그러면 해당 mid(말들 사이의 최대 거리)를 answer에 넣고 더 적합한 값을 찾기 위해 

lt=mid+1을 진행한다.

 

만약 count 메서드의 리턴 값인 말이 들어갈 수 있는 좌표의 개수가 말의 개수보다 적다면 mid를 줄여서 더 적합한 값을 찾아야 하므로 rt=mid-1을 진행한다.

 

역시나 이분 검색은 언젠가 lt가 rt를 능가하므로 lt <=rt조건으로 while문을 돌려서 제일 마지막 answer을 리턴한다.

 

 

이제 count 메서드를 살펴보자.

 

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

 

 

항상 1개의 좌표가 존재하므로 cnt=1로 초기화한다.

ep는 제일 작은 좌표의 값을 넣는다. 그러면 좌표 배열의 길이만큼 반복문을 반복하는데,

만약 i번째 배열 요소 값에서 ep의 차이가 dist보다 크거나 같으면 ep에 현재 i 번째 배열 요소 값을 넣는다.

또한 이때 cnt를 증가시킨다. 이렇게 dist보다 좌표 간 거리의 차이가 크다면 cnt를 증가시킨다.

그리고 반복문이 끝나면 cnt를 리턴하는데 이것이 말이 들어갈 수 있는 좌표들의 개수다.

 

이상으로 포스팅을 마치겠습니다.