[Ch.06 - SortSearch] 10. 마구간 정하기(결정알고리즘)## (+ 시뮬레이션)

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

 

설명

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.*;

public class Main {
	static int[] arr;
	static int n, m;

	static boolean check(int mid) {
		boolean flag = true;
		int cnt = 1;
		int ep = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] - ep >= mid) {
				cnt++;
				ep = arr[i];
				if (cnt == m)
					return flag;
			}
		}
		return flag=false;
	}

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

	static int solution(int n, int m) {
		Arrays.sort(arr);
		int answer = 0;
		int lt = 1;
		int rt = Arrays.stream(arr).max().getAsInt() - Arrays.stream(arr).min().getAsInt();
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (check(mid)) {
				lt = mid + 1;
				answer = mid;
			} else {
				rt = mid - 1;

			}
		}
		return answer;
	}
}

 

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

public class Main {

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

		
		return cnt;
	}

	public int solution(int n, int m, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);

		int lt = 1;
		int rt = Arrays.stream(arr).max().getAsInt() - Arrays.stream(arr).min().getAsInt();

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

		return answer;
	}

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

}

 

 

+) 세련된 풀이

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

public class Main {
	public int count(int[] arr , int site) {
		int cnt=1;
		int ep=arr[0];
		for(int i=1;i<arr.length;i++) {
			if(arr[i]-ep>=site) {
				//같은 경우도 포함
				cnt++;
				ep=arr[i];
			}
		}
		
		return cnt;
	}
	public int solution(int n,int m,int[] arr) {
		int answer=0;
		Arrays.sort(arr);
		int lt=1;
		int rt=arr[n-1];
		//int rt =Arrays.stream(arr).max().getAsInt();
		while(lt<=rt) {
			int mid=(lt+rt)/2;
			if(count(arr,mid)>=m) {
				answer=mid;
				lt=mid+1;
				
			}
			else
				rt=mid-1;
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(T.solution(n,m,arr));
	}
}

 

 

#rt구하기

이분검색을 위해서 정렬을 수행했기 때문에, rt의 값은 arr의 마지막 값과 같다.

//1.
int rt=arr[n-1];

//2.
int rt =Arrays.stream(arr).max().getAsInt();

 

#n개의 마구간의 최소거리가 mid로 배치시킬 수 있는지 확인하는 함수 만들기

: 하나를 배치하고, 그 배치한 마구간으로부터의 거리가 mid보다 같거나 큰 마구간 개수를 이용해 참 거짓 판정

 

1. boolean으로 리턴

static boolean check(int mid) {
    boolean flag = true;
    int cnt = 1;
    int ep = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] - ep >= mid) {
            cnt++;
            ep = arr[i];
            if (cnt == m)
                return flag;
        }
    }
    return flag=false;
}


while (lt <= rt) {
    int mid = (lt + rt) / 2;
    if (check(mid)) {
        lt = mid + 1;
        answer = mid;
    } else {
        rt = mid - 1;

    }
}

2. cnt로 리턴

public int count(int[] arr , int site) {
    int cnt=1;
    int ep=arr[0];
    for(int i=1;i<arr.length;i++) {
        if(arr[i]-ep>=site) {
            //같은 경우도 포함
            cnt++;
            ep=arr[i];
        }
    }

    return cnt;
}


while(lt<=rt) {
    int mid=(lt+rt)/2;
    if(count(arr,mid)>=m) {
        answer=mid;
        lt=mid+1;

    }
    else
        rt=mid-1;
}

---

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    //n개의 마구간, k마리의 말
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    //가장 가까운 두말의 거리가 최대거리
    //마구간 좌표
    //1,2,4,8,9
    //3 -> 1, 4, 9
    Arrays.sort(arr);
    int lt=0;
    int rt= Arrays.stream(arr).max().getAsInt();
    int mid=0;
    int answer=0;
    while(lt<=rt){
      mid=(lt+rt)/2;
      if(check(arr, n, k, mid)){
        answer=mid;
        lt=mid+1;
      }else{
        rt=mid-1;
      }
    }
    System.out.println( answer);
  }
  //n개의 마구간의 최소거리가 mid로 배치시킬 수 있는지 확인하는 함수 만들기

  private static boolean check(int[] arr, int n, int k, int mid){
    int sum=0;
    int cnt=1;
    //맨 앞에는 일단 두고, 그 다음 마구간과의 거리보다 같거나 크면, cnt++
    //개수만 채우면 되므로, 개수가 k개가 되면 true
    int ep=arr[0];
    for(int i=1;i<n;i++){
      if(arr[i]-ep>=mid){
        cnt++;
        ep=arr[i];
        if(cnt==k) return true;
      }
    }
    return false;
  }
}