[JAVA] 알고리즘 문제풀이 기초 - Sorting and Searching-4
Sorting and Searching (결정알고리즘)
마구간 정하기(결정알고리즘)
-
설명 : N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ……, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
-
입력 : 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
-
출력 : 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
-
풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int num = scan.nextInt();
int[] arr = new int[size];
for(int i=0; i<size; i++){
arr[i] = scan.nextInt();
}
System.out.println(t.solution(arr, num));
}
public int solution(int[] arr,int num){
int result = 0;
Arrays.sort(arr);
int lt=1, rt=arr[arr.length-1];
while(lt<=rt){
int mid = (lt+rt)/2;
if(count(arr,mid)<num){
rt = mid-1;
} else {
result = mid;
lt = mid+1;
}
}
return result;
}
private int count(int[] arr, int mid) {
int ep=arr[0], cnt=1;
for(int i=1; i<arr.length; i++){
if((arr[i]-ep)>=mid) {
ep = arr[i];
cnt++;
}
}
return cnt;
}
}
- 정리
- 코드 구현보다 문제가 잘 이해가지 않아 문제설명을 풀이하는데 오래 걸렸던 문제
- 배열을 받고 그걸 마굿간의 번호로 생각한뒤(입력된 배열순서는 전혀 의미없음). 지정된 마굿간수에 말들을 배치한다고 가정. 최대 몇칸간격으로 배치할수 있는가
- 배열의 데이터를 일단 순서대로 정렬함
- 마찬가지로 while문을 통해 반복을 돌고 매번 mid값을 찾아 결정 알고리즘을 실행함
- 배열과 mid값을 count함수(별도로 만듬)에 넘겨 해당 mid간격이상으로 말을 배치했을때 마굿간범위 내에서 원하는 수의 말을 배치할수있는가를 찾아야함
- 이때 endpoint를 만들어서 마지막 지점에서 +mid를 하는 방식으로 건너뛰는범위를 확인 할 수 있음
- 총 말수가 원하는 수보다 작으면 rt를 줄여서 보다 작은수로 다시 체크
- 총 말수가 원하는 수보다 많으면 일단 결과값을 저장한뒤 lt를 높여서 보다 더 효율적인 값이 있는지 체크
- 코드 구현보다 문제가 잘 이해가지 않아 문제설명을 풀이하는데 오래 걸렸던 문제