[Leet code - 347] Top K Frequent Elements ✅

문제

input : 정수 배열 nums, 정수 k

output : 배열에서 중복 된 개수가 많은 순으로 k개의 값을 반환한다.(정확한 순서는 상관 없다.)

 

 

시간 복잡도

이 문제에서 n은 배열의 길이로 최대 $100,000$를 가진다.

각 복잡도를 계산하면 이러하다.

• $n^2 = 10'000'000'000  \ \ \text{불가능}$
• $n \log{n} = 100'000 \times 20 \approx 2'000'000 \ \ \text{가능}$

때문에, $n \log{n}$ 이하부터 고려하면 좋다.

하지만 문제 풀 때 복잡도 계산을 잘못해서 $n \log{n}$제외한 상태에서 풀이를 진행했다..ㅎ

 

 

해결 계획

처음 생각한 방법은 등장 횟수를 저장하는 배열을 만드는 방식이였다.

// table[i] : nums의 값이 i인 원소의 개수
// 음수도 존재하기 때문에 1000을 더하여 사용, -1000 = table[0]
int table[2020] = { 0 };

for (const int data : nums)
{
    table[data + 1000]++;
}

이런 방식으로 구성하려고 했고 저장한 테이블을 순회하여 k만큼의 최대값을 저장하면서 반환하는 방식이였다.

이렇게 되면 복잡도가 $2n$이 되기 때문에 빠르고 가능할거라고 생각했다.

 

근데 최대 값을 저장하는 로직 부분에서, 아래와 같이 최대 값을 하나만 기억하려고 했던걸 생각해서 그런지 k개의 값들을 기억하고 관리하기에는 좀 까다로웠다.

// 너무 단순하게 생각했었던 로직
int maxNum = 0;
for (int i =0 ; i < tableSize; ++i)
{
	maxNum = max(table[i], maxNum);
}

그래서 생각한게, 전체 정렬을 하지 않아도 K개만 잘 꺼내기만 하면 되지 않나? 라는 생각이 들어 우선순위 큐를 고려했다.
복잡도 또한 push와 pop이 log n 이니까 가능하다 생각했다.

 

큐에 저장해야하는 건 값과 등장 횟수 두 가지라 자연스럽게 pair를 생각했다.

기존 배열을 이용해 큐에 저장하려고 했는데 뭔가 번거로웠다.

// 뭔가 번거로움
for (int i = 0; i < table.size(); ++i)
{
	if (table[i] == 0) continue;
	queue.push({table[i], i);
}

 

그래서 대안을 찾다가 해시를 생각했는데, 희소 원소도 제거되고 해시 테이블을 순회 할 때 pair를 반환하니까 한번에 주면 되겠다 싶어서 해시로 변경하여 진행했다.

 

 

구현

vector<int> topKFrequent(vector<int>& nums, int k) {
    // @first : nums의 값
    // @second : first가 nums에 포함된 개수
    unordered_map<int,int> table;

    for (const int data : nums)
    {
        table[data]++;
    }

    // push queue
    priority_queue<pair<int,int>> q;
    for (const auto& data : table)
    {
        q.push({data.second, data.first});
    }

    // pop queue
    vector<int> result;
    result.reserve(k);
    while (k--)
    {
        result.push_back(q.top().second);
        q.pop();
    }

    return result;
}

 

 

되돌아보기

우선순위 큐를 너무 오랜만에 써서 pari형은 직접 정렬 함수를 설정해야 하는줄 알고 뻘짓을 했었다.

first를 먼저 비교, 값이 같다면 second를 비교하는 방식으로 정렬을 자동으로 수행해준다.

 

그리고 덤으로 알게 된건, C++은 기본이 내림차순이고 java는 기본이 오름차순인 것처럼 기본 정렬 순서가 다른 이유는,

각 우선순위에 대한 철학이 달라서 생기는 차이라고 한다! 사실인지는 모르지만.. ㅎ

 

그리고 우선 순위 큐라는 힌트를 나중되서 생각이 들었는데,
굳이 전체 정렬하지 않아도 된다 라는 워드에서 이미 우선순위 큐에 대한 힌트를 준게 아닌가 싶다..!