알고리즘
[백준, 자바, 2110번] 공유기 설치(이분 탐색)
hminor
2024. 8. 24. 11:44
반응형
풀이
- 뭔가 문제를 제대로 이해하지 못했어서 시간이 좀 더 걸린 문제로
- 문제 해결 방법은 정말 단순하게 이분 탐색 문제인데
- 왠지 모르게 지난 풀이 방법으론 해결 방법에 대한 뎁스가 한 개 더 있는 듯한 느낌이었어서
- 더 꼬이게 되어버림...
- 그리고 이분 탐색의 결과 도출에 대한 것으로 하나 상기된 것은
- 결과가 나왔을 경우 계속해서 탐색할 때
- 같을 경우와 부족할 경우를 함께 묶어 처리를 하는 것을 다시 상기하게 되었음.
import java.io.*;
import java.util.*;
public class _2110 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] li = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int n = li[0];
int c = li[1];
// 집 위치 체크
int[] check = new int[n];
for (int i=0; i<n; i++) check[i] = Integer.parseInt(br.readLine());
Arrays.sort(check);
// 이분 탐색 시작
System.out.println(B_Search(check, c));
}
public static int B_Search(int[] check, int c) {
// 이분 탐색 시작
int s = 0;
int e = check[check.length-1]-check[0];
int mx_range = 0;
while (s<=e) {
int m = (s+e)/2;
int cnt = 1;
int now = check[0];
for (int i=1; i<check.length; i++) {
if (check[i]-now >= m) {
cnt++;
now = check[i];
}
}
if (cnt >= c) {
mx_range = Math.max(mx_range, m);
s = m+1;
}
else e = m-1;
}
return mx_range;
}
}