[PriorityQueue][Medium] 973. K Closest Points to Origin

https://leetcode.com/problems/k-closest-points-to-origin/description/

 

2차원의 정점 정보가 주어질 때 원점에서 k 번째까지 가까운 점들을 찾아라. 

 

priory queue를 구성할 줄 안다면 어렵지 않은 문제. 

 

거리, index의 pair data로 queue를 구성해야 한다. 

다만 여기서 거리는 크기의 비교로만 쓰이므로, root 연산은 해지 않아도 된다.(정확할 필요가 없다)

 

코드

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) 
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int q = 0; q < points.size(); ++q)
    {
        int dist = points[q][0] * points[q][0] + points[q][1] * points[q][1];
        pq.push(make_pair(dist, q));
    }

    vector<vector<int>> vRet;
    for (int q = k; q > 0; --q)
    {
        int idx = (pq.top()).second;
        pq.pop();
        vRet.push_back(vector<int>{ points[idx][0], points[idx][1] });
    }
    return vRet;
}

 

 

결과