📌 문제
문제)
도현이의 집 N개가 수직선 위에 있다.
각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다.
최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고,
가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력)
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.
둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력)
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
시간 제한 : 2 초
메모리 제한 : 128 MB
📌 문제 분석❗️
❗️공유기는 가장 왼쪽부터 설치해야 가장 많이 설치할 수 있다.
❗️모든 집에 공유기를 설치했을 때의 최소 갭을 구할 수 있다.
- 그러나 최소 갭을 굳이 구하려면 별도의 최소 갭을 구하는 로직을 짜야하므로 시간 복잡도가 올라간다.
→ 때문에 최소 갭은 1로 설정해서 시작하자.
❗️맨 오른쪽 집 좌표에서 맨 처음 집 좌표를 빼면 최대 갭을 구할 수 있다.
❗️최대 갭과 최소 갭 사이에서 이분 탐색을 진행
❗️현재 집에서 다음 집의 거리(Arr[i] - preValue)가 Gap(mid)보다 크거나 같다면 공유기를 설치할 수 있다.
해당 경우를 카운트 해주자.
❗️카운트 값이 공유기 갯수보다 크거나 같다면,
찾으려는 갭의 크기보다 작거나 같다는 뜻, 해당 결과(Gap)를 변수(result)에 담아주고 startGap 값을 조정해준다.
❗️카운트 값이 공유기 갯수보다 작다면,
찾으려는 갭의 크기보다 크다는 뜻, endGap 값을 조정해준다.
📌 진행
❗️각각의 변수를 입력받고, 집 좌표를 배열에 담아 이분탐색을 위해 정렬해준다.
int N = readInt();
int C = readInt();
int[] wifiArr = new int[N];
for (int i = 0; i < N; i++) {
wifiArr[i] = readInt();
}
Arrays.sort(wifiArr);
❗️lowGap은 1로 임의 지정, highGap은 맨 오른쪽에서 맨 왼쪽을 뺸 값, result에 만족하는 결과 값(midGap)을 담는다.
int lowGap = 1;
int highGap = wifiArr[N - 1] - wifiArr[0];
int result = 0;
❗️wifiArr[i] - preValue(최근에 공유기가 설치된 좌표)와 이분 탐색 중인 midGap을 비교한다.
while (lowGap <= highGap) {
int midGap = (lowGap + highGap) / 2;
int preValue = wifiArr[0];
int count = 1;
for (int i = 0; i < N; i++) {
if (wifiArr[i] - preValue >= midGap) {
preValue = wifiArr[i];
count += 1;
}
}만약 최근에 공유기가 설치된 지점에서 해당 지점의 거리가 갭보다 크거나 같다면 공유기를 설치할 수 있다는 뜻이다. 따라서 공유기가 설치됐으므로 preValue는 해당 지점의 좌표로 최신화하고, 해당 경우 공유기를 설치했으므로 카운트해준다.
❗️공유기 수(C)보다 설치한 공유기 수(count)가 크거나 같다면,
if (count >= C) {
lowGap = midGap + 1;
result = midGap;찾고자하는 최대 갭보다 작거나 같다는 뜻이다.
따라서 갭의 이분 탐색에서 오른쪽 범위를 탐색해야하므로 lowGap을 midGap+1로 업데이트하고, midGap을 결과 값에 담는다.
❗️공유기 수(C)보다 설치한 공유기 수(count)가 작다면,
} else {
highGap = midGap - 1;
}찾고자하는 최대 갭보다 크다는 뜻이다.
따라서 갭의 이분 탐색에서 왼쪽 범위를 탐색해야하므로 highGap을 midGap - 1 로 업데이트한다.
❗️마지막 결과 값(result)를 출력
System.out.println(result);
📌 전체 코드
package level22_이분탐색_.Q5_2110;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
int N = readInt();
int C = readInt();
int[] wifiArr = new int[N];
for (int i = 0; i < N; i++) {
wifiArr[i] = readInt();
}
Arrays.sort(wifiArr);
int lowGap = 1;
int highGap = wifiArr[N - 1] - wifiArr[0];
int result = 0;
while (lowGap <= highGap) {
int midGap = (lowGap + highGap) / 2;
int preValue = wifiArr[0];
int count = 1;
for (int i = 0; i < N; i++) {
if (wifiArr[i] - preValue >= midGap) {
preValue = wifiArr[i];
count += 1;
}
}
if (count >= C) {
lowGap = midGap + 1;
result = midGap;
} else {
highGap = midGap - 1;
}
}
System.out.println(result);
}
private static int readInt() throws IOException {
boolean isNegative = false;
int value = 0;
while (true) {
int input = System.in.read();
if(input == ' ' || input == '\n') {
return (isNegative) ? -1 * value
: value;
} else if (input == '-') {
isNegative = true;
} else {
value = value * 10 + (input - 48);
}
}
}
}
📌 참조
댓글