자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 마구간 정하기 (결정 알고리즘)

 

https://hyejin.tistory.com/1248

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 뮤직비디

-> 이전 문제 풀이 

 

 

10. 마구간 정하기 

설명

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

 

 

문제 풀이 1

public int solution(int n, int c, int[] arr)
{
   int answer = 0;
   Arrays.sort(arr);
   
   // 거리를 가지고 이분 검색 해야함 !
   int lt =1, 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 int count(int[] arr, int mid)
{
   int cnt = 1; // 배치한 말의 마리 수
   int ep = arr[0]; // 우선 제일 왼쪽 좌표에 배치
   
   for (int i = 1; i < arr.length; i++)
   {
      if (arr[i] - ep >= mid) {
         cnt++;
         ep = arr[i];
      }
   }
   
   

 

👾 : 결정 알고리즘은 사실 count 함수에 해당하는 부분이 중요하다. count 하는 부분에서 lt와 rt의 거리를 옮길 판단을 해야 하기 때문이다. 그리고 결정 알고리즘 구조는 거의 동일하기 때문 ! 

 

이번에는 결정 알고리즘을 풀 때 범위로 말 사이의 거리를 가지고 구해야 한다. 

따라서 lt에는 1, rt 에는 그 말의 좌표 배열에 가장 마지막 값을 넣어주면 된다. (정렬 후) 

이때 lt를 arr[0] 으로 지정하면 안된다!!! (내가 그럼) 예를 들어 arr이 5 8 9 4 2 이런식이면 정렬한다해도 두 말 사이의 거리가 1이 아닌 arr[0] 2부터 시작할 것이기 때문이다. 

 

public int count(int[] arr, int mid)
{
   int cnt = 1; // 배치한 말의 마리 수
   int ep = arr[0]; // 우선 제일 왼쪽 좌표에 배치
   
   for (int i = 1; i < arr.length; i++)
   {
      if (arr[i] - ep >= mid) {
         cnt++;
         ep = arr[i];
      }
   }
   
   
   return cnt;
}

 

count 함수에는 cnt 변수와 ep 변수를 선언하는데 cnt 변수에는 배치한 말의 수를 나타내고, ep는 가장 왼쪽에 해당하는 말의 좌표 값에 해당한다. 우선 첫번째로 가장 왼쪽에 말을 배치하기 위해 ep에는 arr[0] 의 값을 배치하고, 그 다음 한 마리를 배치한 것이기 때문에 cnt 의 값을 1로 초기화해서 시작한다. 

 

그 다음 for문을 i = 1부터 돌면서 arr[i]에서 ep를 뺀 거리 값이 mid 보다 크거나 같을 경우에는 말을 배치할 수 있기 때문에 cnt의 값을 1 증가시키고, ep에는 이제 그 arr[i] 값을 배치한다. 

이렇게 반복한 다음 cnt 값을 리턴하면 배치한 말의 수가 철수가 가지고 있는 말의 수 c 보다 크거나 같으면 거리를 좀 더 넓힐 수 있다는 뜻이기 때문에 lt의 값을 mid 보다 + 1 해서 시도한다. 

그리고 만약 count 함수가 리턴한 cnt 값이 c 보다 작으면 거리가 너무 넓어서 주어진 말 c 를 모두 배치하지 못했다는 말이기 때문에 rt 의 값을 mid - 1 해서 다시 시도해본다. 

 

이렇게 반복하다 보면 가장 가까운 말의 최대 거리를 구할 수 있다.