Algorithm - Binary Search
- 2023-12-15 에 풀이한 문제
- 풀이 시간 : 10:30 ~ 10:57 ( 풀이 성공 )
- 나의 풀이 깃허브 : 풀이 클릭!
알고리즘 문제(Java) : 마구간 선택하기 ( 이진 트리 )
1. 문제
N개의 마구간이 수직선상에 있습니다.
각 마구간은 x1, x2, x3, ……, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데,
이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
2. 입력
- 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
- 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
3. 출력
- 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
4. 문제 풀이
- 이진 탐색은 정렬된 리스트나 배열에서 검색 범위를 줄여 나가며 검색 값을 찾는 알고리즘이다.
- lt 와 rt 가 꼭 배열 사이의 값이 되는게 아니라, 내가 풀려고 하는 답과 관련된 범위를 지정해주어야 한다.
- 이번 문제에서는 말과 말 사이의 간격이 lt rt가 된다.
- 마굿간 좌표 위치는 따로 보아야 한다.
public class Binary_Search {
public static int count(int[] arr, int distance) {
int ep = arr[0];
int count = 1;
for ( int i=1; i<arr.length; i++ ) {
if ( arr[i] - ep >= distance ) {
ep = arr[i];
count ++;
}
}
return count;
}
public static int solution(int n, int c, int[] arr) {
int answer = 0;
Arrays.sort(arr);
int lt = 1; // 최소 거리
int rt = arr[n-1]; // 최대 거리
while ( lt <= rt ) {
int mid = ( lt + rt ) / 2;
if ( count(arr, mid) >= c ) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int c = scan.nextInt();
int[] arr = new int[n];
for ( int i=0; i<n; i++ ) {
arr[i] = scan.nextInt();
}
System.out.println(solution(n, c , arr));
}
}