LeetCode : 692. Top K Frequent Words

 

문제)

 

문자열 배열 words와 정수 k가 주어진다.

빈도가 높은 문자열 k개를 반환.

빈도가 같은 문자열은 사전순으로 정렬하여 반환.

 

정렬 기준 :
        빈도가 높은 순서대로 정렬.
        빈도가 같은 경우, 사전순(알파벳순)으로 정렬.

 

문제 난이도 : 중

 

소요시간 및 풀이)

난이도가 중인거 치고 되게 빠르고 쉽게 풀었다.

우선 빈도가 높은 순서대로 정렬하면되니까 우선 순위 큐에 빈도를 대상으로 비교해서 넣어주도록 코드를 작성했다.

 

소요 시간 : 16분

 

정답 코드

class Solution 
{
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string, int> map;

        for (auto str : words)
            map[str]++;

        auto comp = [](const pair<string, int>& a, const pair<string, int>& b)
        {
            if (a.second == b.second) 
                return a.first > b.first; 
            
            return a.second < b.second; 
        };

        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(comp)> queue(comp);

        for (const auto& entry : map) 
        {
            queue.push(entry);
        }

        vector<string> result;

        for (int i = 0; i < k && !queue.empty(); ++i) 
        {
            result.push_back(queue.top().first);
            queue.pop();
        }

        return result;
    }
};