[백준 스터디 1주차] 2110번 공유기설치 골드5 - 자바(JAVA) / 이분탐색

📑 문제

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

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 💡 최대한 거리를 벌려서 공유기를 설치하는게 목적이다.

 따라서 공유기를 설치할 거리의 최소값(mid)을 정해놓고, 그 이상이 될 때만 공유기를 설치한다. 그 이하의 거리에서 설치하면, 최대한 거리를 벌리겠다는 목적을 상실하는 것이다.

 이번 이분탐색에서 조절하는 것이 바로 이 최소값이다.

 

houses = new int[N];
for (int i = 0; i < N; i++) {
	houses[i] = Integer.parseInt(br.readLine());
}//input
Arrays.sort(houses);

 N개의 집이 위치한 좌표를 저장해두는 배열을 만들고, 오름차순으로 정렬한다.

 따라서 house[0]이 제일 왼쪽에 위치한 집, house[N-1]이 제일 오른쪽에 위치한 집이 될 것이다.

 

 여기서부터는 이제 이분탐색을 시작한다.

 처음 mid값은 최대기준거리로, 마을 전체 길이(첫 번째 집과 마지막 집 사이의 거리)/2로 설정한다. 

 

 

 

 

 

✔️ 예를 들어 N=4이고, C=3, 각 집의 위치가 [10,15,40,50]이라고 할 때를 생각해본다.

 처음 mid값은 처음 집과 마지막 집 사이의 중간거리인 (10+50)/2=30일 것이다.

 ◻️ 처음 공유기 설치 위치는 첫 번째 집의 위치인 10이 된다.

 ◻️ 두 번째 집인 15의 경우, 이전 집 10과의 거리차가 5밖에 되지 않으므로 기준길이인 30을 넘지 못하여 공유기를 설치하지 않는다.

 ◻️ 세 번째 집인 40의 경우 이전 집 10과의 거리차가 30이므로 기준을 만족하여 공유기를 설치할 수 있다. 이때 기준위치는 새로 공유기를 설치한 위치인 40으로 옮겨간다.

 ◻️ 마지막 집인 50의 경우 이전 집 40과의 거리차이가 10밖에 되지 않으므로 공유기를 설치하지 않는다.

 

 공유기를 두 개 설치했으므로 목표값 3보다 모자라다. 즉, 거리를 너무 벌려서 설치했다는 뜻이다.

 이럴 때에는 기준길이를 좁혀서 다시 탐색을 시도해본다.

 

if(cnt>=C) {//집 사이 거리를 적당히 설정했을 때
	result = mid;
				
	//최적의 해를 위해 간격을 더 넓혀본다
	left = mid+1;
}else {//집 사이 거리를 너무 넓게 설정했을 때
	//간격을 더 좁혀본다.
	right = mid-1;
}

 

 

 

 

 

 

🙋‍♀️ 의견

 수학을 전혀 못하는 나로서는 mid값을 조율할 때 왜 left=(mid+1)/ right=(mid-1)같이 푸는 것인지 이해하지 못했다...

 거리를 좁히려면 left+1이나 right-1로 해도 되잖아? 

 하지만 직접 찍어보니 성능에 있어서 정말 큰 차이가 생긴다.

 이분탐색의 의의를 전혀 생각해보지 못했다는 증명....(^^)

 찔끔찔끔 조율하는 것보다 이분탐색으로 주어진 값에서 크게크게 옮겨가는 것이 훨씬 성능에 좋다.

 그냥 외우자!!!

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

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

// 이분탐색, 매개 변수 탐색
public class Main_백준_2110_공유기설치_골드V {

	static int N, C;
	static int[] houses;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		houses = new int[N];
		for (int i = 0; i < N; i++) {
			houses[i] = Integer.parseInt(br.readLine());
		}//input
		Arrays.sort(houses);

		
		//1.완전탐색
		/*int max = houses[N-1]-houses[0]; //최대간격
		int dist = 1; //시작간격
		
		while(dist<=max) {
			// 첫 번째 공유기
			int cnt = 1;
			int before_pos = houses[0];
			
			// 공유기 설치작업
			for (int i = 1; i < N; i++) {
				// 간격이 공유기를 설치할 수 있는 정도라면
				if(houses[i]-before_pos >= dist) {
					cnt++;
					before_pos = houses[i];
				}
			}
			
			if(cnt<C) break;
			dist++;
		}
		System.out.println(dist-1);*/
		
		//2.이분탐색
		int result = 0;
		int left = 0;
		int right = houses[N-1]-houses[0]; //최대간격
		
		while(left<=right) {
			// 첫 번째 공유기
			int cnt = 1;
			int before_pos = houses[0];
			
			// 집 사이 거리 -> 이분탐색에서 조절할 변수
			int mid = (right+left)/2;
			
			// 공유기 설치작업
			for (int i = 1; i < N; i++) {
				if(houses[i]-before_pos >= mid) {
					cnt++;
					before_pos = houses[i];
				}
			}
			
			if(cnt>=C) {//집 사이 거리를 적당히 설정했을 때
				result = mid;
				
				//최적의 해를 위해 간격을 더 넓혀본다
				left = mid+1;
			}else {//집 사이 거리를 너무 넓게 설정했을 때
				//간격을 더 좁혀본다.
				right = mid-1;
			}
		}
		
		System.out.println(result);
	}//end of main
}//end of class

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨