문제 개요
정렬되지 않은 배열 A가 주어져 있다고 가정해 봅시다. 여기에 두 개의 값 X와 k가 함께 주어지며, 우리의 목표는 배열 A에서 X에 가장 가까운 k개의 원소를 찾아내는 것입니다.
단, 만약 X 자체가 배열에 포함되어 있다면 그 값은 결과에서 제외해야 합니다.
예를 들어 다음과 같은 입력이 있다고 해보겠습니다.
- 배열 A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56]
- X = 35, k = 4
이 경우 출력 결과는 30, 39, 42, 45가 됩니다. 이 네 숫자는 35와의 차이가 가장 작은 원소들이기 때문입니다.
해결 접근 방식: 최대 힙(Max-Heap) 활용
이 문제는 힙(Heap) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 전체 배열을 정렬하는 대신, 크기가 k인 최대 힙만 유지하면 되기 때문입니다. 알고리즘의 단계는 다음과 같습니다.
처음 k개의 원소에 대해 |원소 − X| 값을 기준으로 최대 힙을 구성합니다.
(k+1)번째 원소부터 마지막 원소까지 다음 과정을 반복합니다.
- 현재 원소와 X 사이의 차이(절댓값)를 계산합니다.
- 이 차이가 힙의 루트(최대값)보다 크다면, 현재 원소는 후보에서 벗어나므로 무시합니다.
- 그렇지 않다면, 힙의 루트를 제거하고 현재 원소를 새로 삽입합니다.
모든 원소를 순회한 후, 힙에는 X와 가장 가까운 k개의 원소만 남게 됩니다.
C++ 구현 예제
#include <iostream>
#include<queue>
using namespace std;
void findKClosestNumbers(int arr[], int n, int x, int k) {
priority_queue<pair<int, int> > priorityQ;
for (int i = 0; i < k; i++)
priorityQ.push({ abs(arr[i] - x), i });
for (int i = k; i < n; i++) {
int diff = abs(arr[i] - x);
if (diff > priorityQ.top().first)
continue;
priorityQ.pop();
priorityQ.push({ diff, i });
}
while (priorityQ.empty() == false) {
cout << arr[priorityQ.top().second] << " ";
priorityQ.pop();
}
}
int main() {
int arr[] = {48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56};
int x = 35, k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
findKClosestNumbers(arr, n, x, k);
}실행 결과
45 42 30 39 35
위 예제에서는 k = 5로 설정했기 때문에, 35와 가장 가까운 5개의 숫자인 45, 42, 30, 39, 35가 출력됩니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O((n−k) × log k)입니다. 처음 k개의 원소로 힙을 구성하는 데 O(k log k)가 소요되고, 이후 나머지 (n−k)개의 원소 각각에 대해 최악의 경우 한 번의 pop과 push 연산(O(log k))이 발생하기 때문입니다. 배열 전체를 정렬하는 방식(O(n log n))보다 k가 n에 비해 작은 경우 훨씬 효율적이라는 장점이 있습니다.