🧩 문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제
입력
5 3
1
2
8
4
9출력
3🎯 풀이
| 메모리 | 시간 | 코드길이 |
|---|---|---|
| 28052 KB | 256 ms | 1739 B |
Point
이분탐색 중 거리를 늘릴지 줄일지를 판단하는 조건이 공유기를 설치하는 개수이다.
1. 이분탐색
while(min < max) {
int middle = (min + max) / 2;
//1. 설치할 수 있는 공유기의 개수가 설치해야하는 개수보다 적을 경우
if(cntInstall(middle) < C) {
max = middle; //거리 좁히기
} else {
min = middle + 1; //거리 늘리기
}
}이분탐색을 진행한다. 공유기 사이의 거리를 좁히는 기준은 파라미터로 넘겨준 거리를 기준으로 공유기를 설치했을 때 C의 개수보다 적을 경우이다. 설치해야하는 공유기 대수보다 적은 수의 공유기를 설치했기 때문에 거리를 좁히는 것이다.
2. 설치할 수 있는 공유기 개수 세기
private static int cntInstall(int distance) {
int cnt = 1;
int lastHouse = houses[0];
for(int i = 1; i < houses.length; i++) {
int curHouse = houses[i];
if(curHouse - lastHouse >= distance) {
cnt++;
lastHouse = curHouse;
}
}
return cnt;
}공유기는 항상 첫번째 집(houses[0])에 설치를 한 후에 마지막으로 공유기를 설치한 집과 현재의 집 사이의 거리가 설정한 거리 이상이라면 현재의 집에 공유기를 설치한다.
⭐️ 전체 풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ2110_공유기설치 {
private 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());
int N = Integer.parseInt(st.nextToken()); //집의 개수
int C = Integer.parseInt(st.nextToken()); //공유기의 개수
houses = new int[N];
for(int i = 0; i < N; i++) {
houses[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(houses); //이분탐색을 하기 위한 정렬
int min = 1; //라우터 최소 거리
int max = houses[N-1] - houses[0] + 1; //라우터 최대 거리
while(min < max) {
int middle = (min + max) / 2;
//1. 설치할 수 있는 공유기의 개수가 설치해야하는 개수보다 적을 경우
if(cntInstall(middle) < C) {
max = middle; //거리 좁히기
} else {
min = middle + 1; //거리 늘리기
}
}
System.out.println(max - 1);
} //Main 끝
//공유기를 몇개 설치할 수 있는지 체크
private static int cntInstall(int distance) {
int cnt = 1;
int lastHouse = houses[0];
for(int i = 1; i < houses.length; i++) {
int curHouse = houses[i];
if(curHouse - lastHouse >= distance) {
cnt++;
lastHouse = curHouse;
}
}
return cnt;
}
}
봉다리