[백준] 2110번 공유기 설치 자바

문제 (이분 탐색)

 

2110번: 공유기 설치

 

 

문제 풀이

 

이분 탐색 알고리즘이다. 이분 탐색 문제를 몇 개 풀면서 느낀 건데 약간 정답의 범위가 정수의 형태로 적당히(?) 정해지는 경우 사용하는 것 같다.

그리고 이분 탐색을 사용할 때, 이분 탐색을 코드를 작성하는 것보다 해당 값에 대해 성립하는지 확인하는 코드짜기가 더 어렵다. 이번 공유기 설치 문제도 이분 탐색으로 정답을 추려가면서 이 정답에 성립하는지를 처리하는 로직이 까다로웠다.

 

✔️알고리즘

1. 집의 좌표를 담은 배열(arr)을 정렬한다.

2. 공유기 사이의 최대 거리가 될 수 있는 범위를 추려 start, end변수에 담는다. (백준 예시 기준: 1 ~ 8)

3. 이분탐색을 진행하며 공유기 간 최소 거리가 mid값이 될 수 있는지 확인하며 범위를 조절해 나간다.

4-1. 해당 mid로 공유기 설치가 가능하면 더 큰 값으로 범위를 잡는다 (start = mid + 1)

4-2. 공유기 설치가 불가하면 더 작은 값으로 범위를 추린다 (end = mid - 1)

 

✔️공유기 설치 가능 판별 알고리즘

1. 정렬된 수직선 상에 집에서 우선 첫번째 집에는 공유기를 설치한다

2. 그리고 현재 설치한 공유기를 담는 cur변수에 저장한다

3. cur변수를 기준으로 다음 집에 공유기를 설치할 수 있는지 확인한다 : 최소값(mid)를 넘어가는지

4. 설치가능하다면 count변수 증가, cur변수를 해당 집으로 갱신

5. count변수가 가지고 있는 공유기 개수보다 같거나 커지면 설치가 가능하다.

왜냐하면, 현재 집 기준으로 다음 집에 최소 거리가 넘어서 공유기 설치가 가능하다면 다음 집 이후로 나오는 집은 무조건 공유기 설치가 가능하다. 그래서 그 다음집에서 설치가 가능하면 거기서 빨리 설치를 하고, 설치한 집을 기준으로 다음 집 설치 유무를 확인해야 적어도 필요한 공유기 개수를 구할 수 있다. 그래서 이 공유기 개수로 가능한지 여부를 판단할 수 있다.

 

 

소스 코드

 

public class b_2110 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		int answer = 0;
		int N = Integer.parseInt(str[0]);	//집 개수
		int C = Integer.parseInt(str[1]);	//공유기 개수
		int[] arr = new int[N];				//집의 x좌표
		
		for(int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		Arrays.sort(arr);
		
		int start = 1;
		int end = arr[N-1] - arr[0];
		int mid = 0;
		
		while(start <= end) {
			mid = (start + end) / 2;
			int count = 1; 	//공유기 설치 개수
			int cur = arr[0];	//가장 첫번째 집 설치
			
			//해당 mid값이 가장 인접한 공유기의 값이 되는지 확인 -> 공유기 간 거리에서 mid가 최소가 되어야
			for(int i = 1; i < N; i++) {
				if(arr[i] - cur >= mid) {
					count++;
					cur = arr[i];
				}
			}
			
			if(count >= C) { //설치할 수 있으므로 공유기 거리를 더 넓히기
				start = mid + 1;
				answer = mid;
			}
			else	//mid값이 사이가 되도록 공유기 설치를 못하므로 거리를 줄여야 함
				end = mid - 1;
		}
		
		System.out.println(answer);
	}

}