섹션6. Sort - 10. 마구간 정하기(결정알고리즘)

📌 문제 설명

N개의 마구간이 수직선상에 존재합니다. 각 마구간의 좌표는 모두 다릅니다.

현수는 C마리의 말을 가지고 있으며, 말들은 서로 가까이 있는 것을 싫어합니다.
한 마구간에 한 마리의 말만 넣을 수 있으며, 가장 가까운 두 말 사이의 거리를 최대한 크게 하고자 합니다.

목표: 말을 배치했을 때 가장 가까운 두 말 사이의 거리의 최대값을 구하시오.

---

📝 입력 & 출력

입력

• 첫 줄: 자연수 N(3≤N≤200,000)과 C(2≤C≤N)
• 둘째 줄: N개의 마구간 좌표 (0≤xi≤1,000,000,000)

출력

• 첫 줄에 가장 가까운 두 말 사이의 최대 거리를 출력합니다.

---

🔹 예제 입력 & 출력

예제 입력 1

5 3
1 2 8 4 9

 

예제 출력 1

3

 

예제 해설

• 1, 2, 4, 8, 9 중에
• 1번 마구간에 말 배치
• 4번 마구간에 말 배치 (거리 3)
• 8번 마구간에 말 배치 (거리 4)
• 가장 가까운 두 말 거리 = 3

---

💡 해결 방법

• 마구간 좌표를 오름차순 정렬한다.
• 이분 탐색을 이용해 가능한 거리의 최대값을 찾는다.
  • lt = 1, rt = 가장 끝 좌표 값
  • mid 거리로 말을 배치할 수 있는지 시도한다.
  • 말 배치가 가능하면 거리(mid)를 늘려보고, 불가능하면 줄인다.

---

💻 코드 구현 (Java)

package partSort;

import java.util.Arrays;
import java.util.Scanner;

public class Problem10 {
	public int count(int[] arr, int dist) {
		int cnt=1, ep=arr[0];
		for(int i=1; i<arr.length; i++) {
			if(arr[i]-ep>=dist) {
				ep = arr[i];
				cnt++;
			}
		}
		return cnt;
	}
	
	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 static void main(String[] args) {
		Problem10 T = new Problem10();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int c = kb.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++) arr[i]=kb.nextInt();
		System.out.print(T.solution(n, c, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 거리 계산

public int count(int[] arr, int dist) {
	int cnt=1, ep=arr[0];
	for(int i=1; i<arr.length; i++) {
		if(arr[i]-ep>=dist) {
			ep = arr[i];
			cnt++;
		}
	}
	return cnt;
}

• 최소 거리 dist를 만족하면서 말을 몇 마리 배치할 수 있는지 계산하는 함수입니다.
• 첫 번째 마구간에 말을 놓고 시작합니다.
• 이후, 직전 말보다 dist 이상 떨어진 마구간에만 말을 놓습니다.

2️⃣ 이분 탐색

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;
}

• 가능한 최소 거리(lt)와 최대 거리(rt)를 잡고 이분 탐색을 시작합니다.
• mid 거리로 말을 배치해보고,
  • 말을 다 배치할 수 있으면 → 거리를 늘려본다 (lt = mid + 1)
  • 말을 다 배치 못하면 → 거리를 줄인다 (rt = mid - 1)
• answer에는 말을 배치할 수 있었던 가장 큰 거리(mid)를 저장합니다.

---

⏳ 시간 복잡도 분석

• 정렬: O(N log N)
• 이분 탐색: O(log (10^9)) 
• 거리 검증(count 함수): 매번 O(N)
• 전체 시간 복잡도는 O(N log N + N log (10^9)) → N이 최대 200,000까지 가능해도 충분히 통과합니다..

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런