K차원 공간에 서로 다른 n개의 점이 있다고 가정해 보겠습니다. 여기서 n은 2 이상 10^5 이하의 범위를 가지며, 차원의 개수 k는 1부터 5 사이입니다. 우리가 구해야 할 것은 결과 점에서 n개의 점까지의 맨해튼 거리(Manhattan Distance)의 합이 최소가 되는 점입니다.
두 점 P1(x1, y1)과 P2(x2, y2) 사이의 맨해튼 거리는 |x1 – x2| + |y1 – y2|로 정의됩니다. 예를 들어 차원이 3이고 세 개의 점 (1, 1, 1), (2, 2, 2), (3, 3, 3)이 주어진 경우, 출력은 (2, 2, 2)가 됩니다.
접근 방법: 각 차원의 중앙값 활용
이 문제를 해결하는 핵심 아이디어는 간단합니다. 맨해튼 거리는 각 축(차원)의 거리를 독립적으로 더하는 방식이므로, 각 차원별로 거리의 합을 최소화하는 값을 찾으면 전체 합도 최소화됩니다.
일직선 위의 숫자들에 대해 절댓값 거리의 합을 최소화하는 지점은 바로 중앙값(median)입니다. 따라서 다음과 같은 알고리즘을 사용할 수 있습니다.
- K개의 차원 각각에 대해 해당 좌표들을 오름차순으로 정렬합니다.
- 정렬된 각 차원에서 인덱스 ceil(n/2) - 1 위치의 값(중앙값)을 결과 점의 좌표로 선택합니다.
C++ 구현 예제
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
void minimizeManhattan(int n, int k, vector<vector<int>>& pointList) {
// k개의 모든 차원에 대해 정렬
for (int i = 0; i < k; ++i)
sort(pointList[i].begin(), pointList[i].end());
// 각 차원의 중앙값을 출력
for (int i = 0; i < k; ++i)
cout << pointList[i][(ceil((double)n / 2) - 1)] << " ";
}
int main() {
int n = 4, k = 4;
vector<vector<int>> point = { { 1, 5, 2, 4 },
{ 6, 2, 0, 6 },
{ 9, 5, 1, 3 },
{ 6, 7, 5, 9 } };
minimizeManhattan(n, k, point);
}실행 결과
2 2 3 6
동작 원리 살펴보기
예제에서 첫 번째 차원의 좌표 {1, 5, 2, 4}를 정렬하면 {1, 2, 4, 5}가 되고, ceil(4/2) - 1 = 1번째 인덱스의 값인 2가 선택됩니다. 같은 방식으로 나머지 차원들도 처리되어 최종적으로 (2, 2, 3, 6)이라는 결과 점을 얻습니다.
이 알고리즘의 시간 복잡도는 각 차원마다 정렬을 수행하므로 O(k × n log n)이며, n이 최대 10^5, k가 최대 5인 조건에서도 효율적으로 동작합니다. 점의 개수가 짝수일 때는 두 중앙값 사이의 어떤 점이든 거리의 합이 같지만, 이 구현에서는 일관성을 위해 위쪽 중앙값을 선택합니다.