이 문제에서는 같은 직선 위에 놓여 있는 n개의 점으로 구성된 배열이 주어집니다. 목표는 이 배열에서 k개의 요소를 선택·배치하여 요소들 사이의 최소 거리가 최대화되도록 만드는 것입니다.
문제 예시
예제를 통해 문제를 살펴보겠습니다.
입력 − array = {3, 5, 6, 9, 1, 8}, k = 3
출력 − 4
설명 − 배열을 오름차순으로 정렬하면 {1, 3, 5, 6, 8, 9}가 됩니다. 3개의 요소를 골라 서로 간 최소 거리를 가장 크게 만들려면 1, 5, 9를 선택해야 하며, 이때 인접한 요소 사이의 거리는 각각 4이므로 최소 거리는 4가 됩니다.
해결 접근 방식
이 문제의 핵심은 '달성 가능한 최대 최소 거리'를 찾는 것입니다. 특정 거리 d에 대해 요소들을 d 이상의 간격으로 배치할 수 있는지 판단하는 것은 비교적 쉽지만, 최적의 d를 직접 구하기는 어렵습니다. 따라서 다음과 같은 전략을 사용합니다.
- 먼저 주어진 배열을 오름차순으로 정렬합니다.
- 탐색 범위의 중간값(mid)을 후보 최소 거리로 삼고, 해당 거리 이상의 간격을 유지하며 k개의 요소를 배치할 수 있는지 그리디하게 확인합니다.
- 배치가 가능하면 정답 후보를 갱신하고 더 큰 거리를 탐색하고, 불가능하면 더 작은 거리를 탐색합니다.
- 이진 탐색이 종료되면 지금까지 찾은 최댓값이 곧 정답이 됩니다.
이처럼 결정 문제를 반복적으로 풀어 최적값을 찾는 기법을 매개변수 탐색(parametric search)이라고 부르며, 시간 복잡도는 O(n log m)(m은 최대 좌표 값) 수준으로 매우 효율적입니다.
구현 예제
위 접근 방식을 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
// 거리 mid 이상의 간격으로 k개 요소 배치 가능 여부 검사
bool canGenerateResult(int mid, int arr[], int n, int k) {
int pos = arr[0];
int elements = 1;
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
pos = arr[i];
elements++;
if (elements == k)
return true;
}
}
return false;
}
// 이진 탐색으로 최대화된 최소 거리 계산
int maxMinDist(int arr[], int n, int k) {
sort(arr, arr + n);
int res = -1;
int left = arr[0], right = arr[n - 1];
while (left < right) {
int mid = (left + right) / 2;
if (canGenerateResult(mid, arr, n, k)) {
res = max(res, mid);
left = mid + 1;
} else
right = mid;
}
return res;
}
int main() {
int arr[] = {3, 5, 6, 9, 1, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "최대화된 최소 거리 : " << maxMinDist(arr, n, k);
return 0;
}
출력 결과
최대화된 최소 거리 : 4
코드 설명
canGenerateResult() 함수는 주어진 거리 mid를 유지하면서 k개의 요소를 배치할 수 있는지 확인합니다. 첫 번째 요소부터 시작해 이전에 배치한 위치와의 거리가 mid 이상일 때마다 새 요소를 배치하며, k개를 모두 배치하면 true를 반환합니다.
maxMinDist() 함수는 배열을 정렬한 뒤 최솟값과 최댓값 사이에서 이진 탐색을 수행합니다. 배치에 성공하면 결과를 갱신하고 탐색 범위를 오른쪽으로, 실패하면 왼쪽으로 좁혀 나가 최종적으로 최대화된 최소 거리를 반환합니다.