LeetCode (C/C++) 347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

 

---

풀이

map에 nums에 있는 원소별로 개수를 구한 후 저장한다.

이후에

코드 1 : 벡터에 값을 저장 후 정렬

코드 2 : 우선순위 큐에 값을 저장

하여 반환해줬다.

 

우선순위 큐는 값을 넣을 때마다 정렬을 해야 해서 더 느릴 것이라 생각했는데, 제출된 답안을 보니 더 빨랐다.

근데 내가 낸 건 더 느림 왜지..

---

코드 1

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m;
        vector<vector<int>> v;
        vector<int> ans;

        // map에 값 저장
        for (int n : nums)
            m[n]++;

        // 벡터에 값 삽입 후 정렬
        for (auto iter = m.begin(); iter != m.end(); iter++)
            v.push_back({iter->second, iter->first});

        sort(v.rbegin(), v.rend());

        // return할 k개의 값 추출
        for (int i = 0; i < k; i++)
            ans.push_back(v[i][1]);

        return ans;
    }
};

 

코드 2

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m;
        priority_queue <pair<int, int>> pq;
        vector<int> ans;

        // map에 값 저장
        for (int n : nums)
            m[n]++;

        // 우선순위 큐에 삽입 및 정렬
        for (auto iter = m.begin(); iter != m.end(); iter++)
            pq.push({iter->second, iter->first});

        // return할 k개의 값 추출
        for (int i = 0; i < k; i++) {
            ans.push_back(pq.top().second);
            pq.pop();
        }

        return ans;
    }
};