[Leet code - 973] K Closest Points to Origin ✅

문제

Input : point 배열 points, 정수 k

Output : points에서 원점(0, 0)과 가까운 순으로 k개의 좌표 반환

※ $point = [x, y]$

 

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

$1 \le n \le 10'000$

• $n^2 = 100'000'000$ ❓
  1초에 1억번을 대략적인 기준으로 삼고 있는데, 딱 1억이어서 통과 여부에 대해 위험하므로 일단은 후순위로 고려해둔다.
• $n \log{n} = 10'000 * 14 = 140'000$ ✅
  충분히 안전하기 때문에, $n \log{n}$이하의 접근을 목표로 하면 된다.

 

해결 계획

"~순으로". "순서 관계없이" 라는 단어를 보자마자 우선순위 큐가 생각났다.

배열을 한 번 순회하면서 큐의 거리를 계산해 저장하고, k만큼 꺼내는 방식이 진행할 수 있을 것 같았다.

이 경우 복잡도는 $O(n \log n)$ 으로 충분히 통과 가능하다.

 

아래는 풀이하기전 작성해 본 수도코드다.

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
	
    // 우선순위 큐 <pair<크기, 좌표>>

    for (auto data : points)
    {
        // 벡터 크기 계산
        /* 크기의 범위는? 최대 10'000'000 => int안에서 로 충분 */

        // 크기+좌표 큐에 삽입 (오름차순으로)
    }

    // 결과 vector <vector<int>>
    while (k--)
    {
        // 큐 꺼내서 결과 벡터에 삽입
        /* k <= points.size 이므로 큐가 빈상태에서 꺼낼 일은 없음 */
    }

    return result;
}

 

 

구현

using piv = pair<int,vector<int>>;

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {

    priority_queue<piv, vector<piv>, greater<piv>> q;

    for (auto& data : points)
    {
        int size = (data[0] * data[0]) + (data[1] * data[1]);
        q.push({size, data});
    }

    vector<vector<int>> result;
    result.reserve(k);
    while (k--)
    {
        result.push_back({q.top().second[0], q.top().second[1]});
        q.pop();
    }

    return result;
}

 

 

되돌아보기

sort vs priority queue

다른 사람들의 코드를 보다가 정렬을 이용해 풀이한 사람도 있었는데,

우선순위 큐보다 더 빠른 속도로 실행됐는데, 같은 n log n 방식에서 왜 더 빠르게 실행되었는지 궁금하여 이에 대해 좀 알아보았다.

 

우선순위가 더 느렸던 주요인은,

연속된 메모리를 한 번에 정리해버리는  sort와 달리 , 우선순위 큐는 트리 구조로 원소 수만큼 정렬(swap)을 반복하기 때문에

이번 상황에서는 좀 더 불리했다.

 

또한 연속 메모리가 아니기 때문에 캐시 친화성이 떨어지는 것도 한 몫한다고 볼 수 있겠다.

 

"그럼 언제 sort를 사용하고, 언제 우선순위 큐를 사용해야할까?"에 대해 내린 결론은 다음과 같다.

• Sort
  정렬 한 번으로 끝낼 수 있으면 sort가 유리.
• Priority queue
  데이터가 계속 변하며, 중간중간 top을 꺼내야할때는 우선순위 큐가 유리.
  우선순위 큐는 정렬도구가 아니라 동적 우선순위 자료구조임을 명심하자~

 

개선 코드

vector 복사 회피

내가 작성한 코드에서 vector를 복사하는 대신에, index를 넣어 원본을 사용하는 방식이다.

// first : vec2 Size | second : points index
using pii = pair<int,int>;

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    
        priority_queue<pii, vector<pii>, greater<pii>> q;

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

        vector<vector<int>> result;
        result.reserve(k);

        while (k--)
        {
            result.push_back(points[q.top().second]);
            q.pop();
        }

        return result;
    }
};

 

n log n ⇒ n log k

나는 좀 쓸모 없이 모든 원소를 계속 넣고 있었는데, 큐에서 k개만 필요하다면 k개만 유지해도 될 일이였다.

 

하지만 내 코드에서는 Min-heap을 사용하여 무작정 루트를 삭제 할 수 없었는데,

우선순위 큐의 내부에서는 정렬이 되지 않기 때문에 정답이 되는 노드가 잘릴 수도 있기 때문이다.

 

그래서 루트노드를 최순위로 꺼내야하는 노드가 아닌, 최후순위로 꺼내야하는 노드로 변경해주면

크기가 k개를 넘었을 때 루트를 삭제해줄 수 있다.

 

이는 기존 Min-heap에서 Max-heap으로 변경하면 해결 가능하다.

priority_queue<int> maxHeap;

if (k < maxHeap.size()) maxHeap.pop();

 

nth_element 사용_1

다른 사람의 코드를 보면서 처음 알게 된 함수인데, std::nth_element 라고 Quick sort의 편의성 버전이다.

nth_element는 특정 index를 지정하고, 해당 index의 값이 정렬이 끝나면 종료한다.

 

그래서 결과값으로 지정한 index는 정확하게 정렬이 되었지만, 앞과 뒤 부분은 정렬되지 않는다.

하지만 앞 부분은 지정한 index의 값보다 작은 값들, 뒷 부분은 지정한 index의 값보다 큰 값들로 구성되는 특성을 이용해 볼 수 있다.

 

이 특성은 이 문제에 굉장히 효율적며, 실제로 평균 O(n)을 가지기 때문에 빠른 편에 속한다.

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        
        for (auto& data : points)
        {
            int size = (data[0] * data[0]) + (data[1] * data[1]);
            data.push_back(size);
        }

        nth_element(points.begin(), points.begin() + k - 1, points.end(),
            [](const vector<int>& v1, const vector<int>& v2){return v1[2] < v2[2];}
        );

        vector<vector<int>> result;
        result.reserve(k);

        for (int i = 0; i < k; ++i)
        {
            points[i].pop_back();
            result.push_back(points[i]);
        }

        return result;
    }
};

주의할 건, zero based문제로 nth_element를 사용할 때 points.begin() + k - 1을 사용해야한다. 

 

여기서 push_back이나 pop_back 같은 메모리에 대한 연산을 조금 더 최적화 하면 아래와 같다.

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) 
{
	nth_element(points.begin(), points.begin() + k, points.end(),
	    [](const vector<int>& v1, const vector<int>& v2) 
	    {
	        return v1[0]*v1[0] + v1[1]*v1[1] < v2[0]*v2[0] + v2[1]*v2[1];
	    }
	);
    
	return vector<vector<int>>(points.begin(), points.begin()+k);
}

이 코드는 size를 정렬 과정에서 계속 사용하여 좀 회피하려고 헀었는데,
이런 몇 번의 정수 곱같은 산술 연산은 비용이 저렴한 축에 속하고,
push_back이나 pop_back같은 메모리 변경 연산은 보다 비싼축에 속한다.

 

그래서 지금은 아래의 코드가 더 효율적인 코드라고 볼 수 있고,

만약 sqrt처럼 비교 연산이 매우 비싼편이라면, 위의 코드처럼 미리 값을 저장해 이용하는 방식이 더 유리하다.

 

근데 nth_element는 C++98부터 포함되어 있다고 하는데, 왜 이제 알았을까..?!

참고로 람다는 C++11부터 같이 사용할 수 있다!