[이분 탐색, 결정 알고리즘] 마구간 정하기 .java
설명
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3,......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
입력
첫 줄에 자연수 N(3<=N<=200,000)과 C(2 <=C <=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
출력
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
예시 입력 1
5 3
1 2 8 4 9
예시 출력 1
3
내 풀이
기준은 두 마구간 사이의 거리
- 초기 설정
lt = 최소 거리인 1
rt = 최대 좌표 - 최소 좌표
맨 처음 말을 배치하는 마구간은 배열의 0번 인덱스
- 이분 탐색 및 mid 거리 확인
mid = (lt + rt) / 2 로 현재 입력받은 배열의 마구간 좌표들에서 mid값을 거리로 가질 때 c개의 말을 배치할 수 있는지 확인!
mid = 4면 (예시) arr[0] + 4(mid)한 거리 값보다 크거나 같은 좌표가 있는지 확인
-> 가능한 마구간이 c개이면 정답 업데이트 및 lt = mid +1로 증가한 것도 확인 -> check함수로 구현
-> 왜? 구해야하는 것은 거리의 최댓값이기 때문
만약, 가능한 마구간이 c보다 작으면 말이 다 들어갈 수 없음을 의미
=> 거리가 너무 큼
=> rt = mid -1
- check 함수
말을 m거리 이상으로 배치할 수 있는지 확인하는 함수, 시작은 0번 인덱스부터
-> 말을 배치한 이전 좌표 (index) 값 + mid 이 좌표 배열의 한 거리보다 작거나 같으면 배치할 마구간이 있기 때문에 배치한 말의 개수 증가
=> 배치한 말의 개수가 c일 때 참을 리턴
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c = sc.nextInt();
int[] arr= new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
Arrays.sort(arr);//오름차순 정렬
int lt = 1;
int rt= arr[n-1] -arr[0];//최댓값 - 최솟값
int answer = 0;
while(lt <= rt) {
int mid = (lt + rt) / 2;
if(check(mid,arr,c)) {//해당 거리로 말을 배치할 수 있는지 확인
answer = mid;
lt = mid + 1;//더 큰 거리로 탐색
} else rt = mid -1;//불가능하다면 거리를 줄여서 탐색
}
System.out.print(answer);
}
//말을 mid 거리 이상으로 배치할 수 있는지를 확인하는 함수
public static boolean check(int mid, int[] arr, int c) {
int cnt = 1;//배치한 말의 개수 (첫 마구간에 말을 배치함)
int index = 0;//이전 좌표를 가리키는 인덱스
for(int i = 1; i < arr.length; i++) {
if(arr[index] +mid <= arr[i]) {//이전 마구간 + mid 거리 이상이면 말을 배치
cnt++;
index = i;//현재 마구간을 마지막으로 배치한 마구간으로 설정
if(cnt == c) return true;
}
}
return false;
}
}
다른 풀이
현재 mid 거리일 때 마구간을 배치할 수 있는지 검사하는 함수의 리턴 값이 다르고
현재 좌표에서 이전 좌표를 뺀 값이 mid보다 크거나 같으면 이라고 표현한 점이 다르다
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public int count(int[] arr, int dist) {
int cnt = 1;
int ep = arr[0];//이전 배치한 마구간 좌표
for(int i = 1; i < arr.length; i++) {
if(arr[i] - ep >= dist) {
cnt++;
ep = arr[i];
}
}
return cnt;
}
public 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) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c = sc.nextInt();
int[] arr= new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
System.out.print(T.solution(n,c,arr));
}
}
💡💡
이제 조금 결정 알고리즘에 익숙해진 것 같다
큰 틀은 똑같지만 저 count나 check 함수로 구현하는 부분이 문제마다 다르고 이 부분의 구현이 핵심이라고 생각한다