백준 2110 - 공유기 설치(자바 - 이진 탐색)

중량 제한 문제와 같이 이진 탐색을 통해 해결 할 수 있는 문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

이 문제 또한 공유기 설치 때와 같이 이진 탐색을 어떻게 수행해야 하는지 감이 잡히지 않았으므로 패스트 캠퍼스 코딩테스트 문제 해설 강의를 참고했다.

 

입력 받은 좌표간의 최소 격차, 최대 격차를 각각 start, end 로 잡고 이진 탐색을 수행한다.

- 입력 받은 좌표간의 최소 격차, 최대 격차를 각각 start, end 로 잡고 이진 탐색을 수행해서 해결하는 문제이다.

- 매 반복마다 middle 값을 구한 후 해당 값으로 입력 받은 갯수만큼 공유기 설치가 가능한지 판별한다.

- middle 값으로 지정된 격차 와 같거나 더 크게 떨어져 있는 좌표 들 간에만 공유기 설치가 가능하다.

- 가능한 최대 격차를 구하는데 있어서 입력받은 설치 갯수보다 더 많이 설치 할 수 있으면 격차가 더 커야 하므로 

일단 결과 변수에 middle 값을 저장해주고 난 다음, start 를 middle + 1 로 지정해서 범위를 격차가 더 큰 쪽으로 좁혀준다.

- 입력받은 설치 갯수보다 더 적게 설치 할 수 있으면 격차가 더 작아야 하므로 end 를 middle - 1 로 지정해서 범위를 격차가 더 작은 쪽으로 좁혀준다.

- 반복문이 끝나면 최종적으로 입력받은 설치 갯수를 기준으로 설치 가능한 최대 격차 값을 구할 수 있게된다.

 

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// 가장 인접한 두 공유기 사이의 최대 Gap 을 이진 탐색으로 찾는다.
		// 반복적으로 Gap 을 설정하며, C 개 이상의 공유기를 설치할 수 있는 경우를 찾는다.
		// 1,2,3,8,9 인 경우 최대 Gap : 8, 최소 Gap : 1
		// 최소 gap 과 최대 gap 을 min, max 로 설정한 다음 그 중간값을 반복적으로 찾으면서
		// 그 와 동시에 min, max 값을 조건에 맞게 갱신해주는 방식으로 가능한 최대 Gap 을 찾는다.
		// 설치 가능한 공유기의 수가 C 보다 작으면 Gap 을 감소시키고, C 보다 많으면 Gap 을 증가시킨다.
		// 처음으로 C 개의 공유기 설치가 가능한 gap 을 찾았을 경우, 일단 해당 gap 을 결과로 저장한다음
		// gap 의 값을 1씩 증가시키면서 최대로 가능한 gap 값을 찾는다.
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int arraySize = Integer.parseInt(st.nextToken());
		int router = Integer.parseInt(st.nextToken());
		
		int[] home = new int[arraySize];
		
		for(int i = 0; i < home.length; i++) {
			home[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(home);
		
		int maxGap = home[home.length-1] - home[0];
		int minGap = 1;
		
		int start = minGap;
		int end = maxGap;
		int middle = (start + end) / 2;
		int result = 0;
		
		while(start <= end) {
			int count = 1;
			int standard = home[0];
			middle = (start + end) / 2;
			
			for(int i = 1; i < home.length; i++) {
				if(home[i] - standard >= middle) {
					standard = home[i];
					count++;
				}
			}
			
			if(count >= router) {
				start = middle + 1;
				result = middle;
			}
			else {
				end = middle - 1;
			}
		}
		
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}
}