# K Closest Points to Origin

문제 설명

2차원 평면에서 원점 (0, 0)에 가장 가까운 K개의 점을 찾는 문제

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]

거리는 유클리드 거리를 사용하며, sqrt((x1-x2)² + (y1-y2)²) 공식을 사용합니다. 원점까지의 거리이므로 sqrt(x² + y²)가 되고, 비교만 하면 되므로 제곱근은 생략할 수 있습니다.

풀이 방법

방법 1: Priority Queue (Min-Heap) - 기본 접근

가장 직관적인 방법으로, 모든 점을 힙에 넣고 가장 가까운 k개를 빼내는 방식입니다.

class Solution {
public:
    struct Compare {
        bool operator()(vector<int> a, vector<int> b) {
            return a[0]*a[0] + a[1]*a[1] > b[0]*b[0] + b[1]*b[1];
        }
    };
    
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<vector<int>, vector<vector<int>>, Compare> minHeap;
        
        // 모든 점을 힙에 삽입
        for (auto& point : points) {
            minHeap.push(point);
        }
        
        // 가장 가까운 k개 점 추출
        vector<vector<int>> result;
        for (int i = 0; i < k; i++) {
            result.push_back(minHeap.top());
            minHeap.pop();
        }
        
        return result;
    }
};

시간복잡도: O(n log n)
공간복잡도: O(n)

방법 2: Max-Heap with Size Limit - 최적화된 접근 ⭐

k개만 유지하는 max-heap을 사용하여 메모리와 시간을 절약하는 방법입니다.

class Solution {
public:
    struct Compare {
        bool operator()(vector<int> a, vector<int> b) {
            // max-heap이므로 부등호 방향을 반대로
            return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
        }
    };
    
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<vector<int>, vector<vector<int>>, Compare> maxHeap;
        
        for (auto& point : points) {
            maxHeap.push(point);
            // k개를 초과하면 가장 먼 점(top) 제거
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }
        
        // 결과 추출
        vector<vector<int>> result;
        while (!maxHeap.empty()) {
            result.push_back(maxHeap.top());
            maxHeap.pop();
        }
        
        return result;
    }
};

시간복잡도: O(n log k)
공간복잡도: O(k)

방법 3: 정렬 사용

간단하고 직관적인 정렬 방법입니다.

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
        });
        
        return vector<vector<int>>(points.begin(), points.begin() + k);
    }
};

시간복잡도: O(n log n)
공간복잡도: O(1) - 입력 배열을 직접 수정

성능 비교

방법	시간복잡도	공간복잡도	특징
Min-Heap	O(n log n)	O(n)	직관적, 모든 경우에 동일한 성능
Max-Heap (k개)	O(n log k)	O(k)	k가 작을 때 매우 효율적
정렬	O(n log n)	O(1)	구현이 간단, 메모리 효율적

언제 어떤 방법을 사용할까?

• k << n (k가 매우 작을 때): Max-Heap 방법 사용
• k가 n에 가까울 때: 정렬 방법 사용
• 구현의 단순함을 원할 때: 정렬 방법 사용
• 일반적인 경우: Max-Heap 방법이 가장 효율적

핵심 포인트

1. 거리 비교 시 제곱근 생략: sqrt(x² + y²) 대신 x² + y²만 비교
2. Comparator 방향 주의: Min-heap과 Max-heap의 비교 함수 방향이 반대
3. 메모리 효율성: k개만 유지하는 Max-heap이 가장 효율적