[백준/Java] 2110 공유기 설치

조건

1. 처음에는 집의 개수 N개가 입력된다.

2. 그 후 공유기의 개수 C가 들어온다.

3. 마지막으로 집의 좌표들이 나오는데 그 범위는 (0<=x<=1,000,000,000) 이므로 Int형이다.

4. 한 집에는 하나의 공유기만 설치해야하며 C개가 다 들어갈 때 두 공유기 사이의 최대 거리를 출력하라

예제 입력

해설

이 문제는 N개 만큼의 사이즈를 가진에 A배열에 각 집의 좌표를 넣고 sort를 한후 이분탐색을 통해 해결할 수 있다. 이분 탐색을 통해서 공유기의 개수가 다 들어가지는 최대값을 넣는다면 그 최대값이 두 공유기 사이의 최대 거리가 된다.

코드

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



public class Main {
	
	static int N,C;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		N = scan.nextInt(); // 집의 수를 받는다.
		C = scan.nextInt(); // 공유기의 개수를 받는다
		A = new int[N + 1]; //index를 1부터 시작하기 위해 +1을 해준다.
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextInt(); // 집의 좌표를 받는다.
		}

	}

	
	static boolean findAns(int D) {
		int count =1 , best = A[1];
		for(int i =2;i<=N;i++) {
			if(A[i] - best < D) continue;// 첫번째 집 과 그 다음 집의 거리를 구하고 							         	//해당 거리가 최소거리보다 작은지 확인한다.
			best = A[i]; // 충족을한다면 다음 거리계산을 위한 값을 넣어준다.
			count ++ ; //공유기 개수를 카운트하기 위한 변수
		}
		return count >= C; // 전체 공유기 개수보다 같거나 큰지 확인한다. 

	}
	

	static void find() {
		Arrays.sort(A,1,N+1); // 집 좌표를 오름차순으로 정렬한다.
		int L = 1, R = 1000000000, ans =0; // 이분탐색을 위한 Left값과 Right값을 정											 // 해줌
		
		while(L <=R) {
			int mid = (L + R) / 2; 
			if(findAns(mid)) { //true값이 반환 된다면 
				ans = mid; // mid값을 ans에 저장한후 
				L  = mid + 1; // 다음 탐색을 이어나간다.
			} else { //false값이 나온다면
				R = mid - 1; // R의 범위를 줄이고 다음 탐색을 이어나간다.
			}
		}
		System.out.println(ans); // ans에 저장된 값이 공유기의 설치 개수를 충족하며
        						//  거리가 최대인 값이 저장되어 있다.
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}