[BaekJoon] 2110 공유기 설치 (java)

🔗 문제 링크

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

👨🏻‍💻 작성한 코드

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


public class Main {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int numOfHouse= Integer.parseInt(st.nextToken());
		int numOfWifi = Integer.parseInt(st.nextToken());
		
		int[] house = new int[numOfHouse];

		for (int i=0; i<numOfHouse; i++) {
			house[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(house);

		
		int result = 0; // 최종 답
		int start = 1; // 현재 가능한 최소 이동거리
		int end = house[numOfHouse-1] - house[0]; // 현재 이동가능한 최대 이동거리
		
		
		while (start <= end) {
			int midGap = (start+end)/2;
			int value = house[0];
			int count = 1;
			
			
			for (int i=1; i<numOfHouse; i++) {
				if (house[i] >= (value + midGap)) {
					value = house[i];
					count++;
				}
			}

			if (count >= numOfWifi) { // 더 많은 공유기가 설치될 수 있는 경우
				start = midGap + 1;
				result = midGap;
			}
            		// 공유기 설치 공간이 부족한 경우 
			else end = midGap-1;

		}
		System.out.println(result);
	}
}

📝 코드 설명

문제의 입력 조건을 보면 받을 수 있는 데이터의 양이 매우 많은 것을 확인할 수 있다.

이러한 문제의 경우 데이터를 하나씩 확인하게 된다면 실행시간이 매우 많이 나올 것이다. 문제를 풀 때는 데이터의 개수를 보고 이번 문제와 같이 10억개와 같이 많은 데이터에 대해 돌려야한다면
2진 탐색과 같은 자료구조를 사용하여 $log(N)$와 같은 시간복잡도를 만들도록 출제자가 출제했다는 것을 알아차려야한다!!!

그리하여 이번 문제는 이진탐색을 이용하여 문제를 풀어봤다.

코드의 실행 구조
1. 처음에는 넓은 간격으로 탐색을 한다.
2-1. 탐색을 하였을 때 설치하려는 공유기의 개수보다 적은 개수가 설치됐을 경우 간격을 줄인다.
2-2. 공유기의 개수보다 많이 설치되었을 경우 간격을 넓힌다.