179. 2110(공유기 설치) - 자바

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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int C = sc.nextInt();

		long[] home = new long[N];

		for (int i = 0; i < N; i++) {
			home[i] = sc.nextLong();
		}

		Arrays.sort(home);

		long start = 1;
		long end = home[home.length - 1] - home[0];
		long result = 0;

		while (end - start >= 0) {
			long mid = (start + end) / 2;
			long currentHome = home[0];
			int wifi = 1;

			for (int i = 1; i < home.length; i++) {
				if (home[i] >= currentHome + mid) {
					currentHome = home[i];
					wifi++;
				}
			}

			if (wifi >= C) {
				start = mid + 1;
				result = mid;
			} else {
				end = mid - 1;
			}
		}
		
		System.out.println(end);

	}
}

문제요약

가지고 있는 공유기 개수 만큼 집에 설치 했을 때 두 집의 최대 거리를 구하라.

설명

집이 1 2 4 8 9 에 위치해 있다고 하자.

 

두 집 사이의 거리가 가장 작게 설치되는 거리는 1이다.

두 집 사이의 거리가 가장 크게 설치되는 거리는 9 - 1 로 8이다.

		long start = 1;
		long end = home[home.length - 1] - home[0];
		long result = 0;

 

 

따라서 1~8까지 후보군이며 먼저 mid 값을 8 + 1 / 2 로 4를 설정한다.

오름차순으로 정렬하였고 처음 집부터 설치를 진행한다.

공유기는 end 거리만큼 최소 한개를 설치 할 수 있기 때문에 1로 설정한다.

		while (end - start >= 0) {
			long mid = (start + end) / 2;
			long currentHome = home[0];
			int wifi = 1;

 

 

현재 1을 기준으로 5칸 보다 크고 가장 인접한 집은 8이다.

1번에 설치를 하고 현재 집을 8로 바꾸면 12보다 거리가 큰 곳을 찾아야 하는데 9가 최대로 공유기는 총 2곳에만 설치하게 된다.

			for (int i = 1; i < home.length; i++) {
				if (home[i] >= currentHome + mid) {
					currentHome = home[i];
					wifi++;
				}
			}

 

그러면 4보다 크거나 같은 위치에는 공유기 3개 설치가 불가능하다!

따라서 1~3내에서 공유기 3개를 설치하고 간격이 가장 큰 곳을 찾게 된다.

			if (wifi >= C) {
				start = mid + 1;
				result = mid;
			} else {
				end = mid - 1;
			}
		}

 

이 과정을 반복하며, 공유기 설치 갯수가 도현이가 원하는 만큼보다 크거나 같으면 일단 답으로 저장하며, 시작위치가 끝 위치보다 크거나 같을 때 까지 진행한다.