[c++/LeetCode-Hash Table] 692. Top K Frequent Words

 

 

난이도: Medium

키워드: Hash Table

 

🎲 문제

 

문자열 배열 words와 정수 k가 주어졌을 때, k개의 가장 빈번한 문자열을 반환합니다.
빈도수가 높은 순서대로 정렬된 답을 반환합니다. 동일한 빈도를 가진 문자열은 사전순으로 정렬합니다.

 

 

🎲 예시

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

 

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

 

 

🎲 문제 풀이

hash를 사용해서 count를 해주면 되는 단순한 문제이다.

hash를 사용한 count -> count 값 기준으로 sort -> 그 중 top-k개만 출력 하면 끝나는 문제이다. (쉽죠?)

 

문제 풀이 할 때, 다양한 데이터 구조를 써보자 싶어서 (python으로 코딩문제 풀어보던거 요즘 cpp로 옮겨가는 중이라 STL 익힐 겸) 굳이 안써도 되는 heap을 써봤다. 이 코드에서 heap (priority_queue)는 안써도 되고 sorting 하는 게 오히려 더 맞는 코드이다. heap은 계속해서 sorting이 필요할 때 사용하면 좋은데,  이 코드에서는 사실상 한번에 sorting하는 거라... 그다지 효용성은 없는 코드이다.

 

compare 함수를 넣어줄 때 조심할 점은, sort에 넣어주는 compare는 함수를 정의해주면 되지만, heap 에 들어가는 compare 용 함수는 compare class 내에 operator() 를 오버라이딩해주는 형태로 정의해줘야한다.

 

struct cmp{
    bool operator()(pair<int, string> a, pair<int, string> b) const{
        if(a.first > b.first)
            return !(a.first > b.first);
        if(a.first == b.first)
            return !(a.second < b.second);
        else
            return !(false);
        
    }
};

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

        unordered_map<string, int> hash;
        vector<string> ans;

        // count
        for(const auto word : words){
            const auto ptr = hash.find(word);
            if(ptr == hash.end())
                hash[word] = 1;
            else
                hash[word] += 1;
        }

        // build heap
        priority_queue<pair<int, string>, vector<pair<int, string>>, cmp> heap;
        for(auto const& it: hash){
            cout << it.first << " " << it.second << endl;
            heap.push({it.second, it.first});
        }

        // find top k elements
        for(auto _ = 0; _ < k; ++_){
            ans.emplace_back(heap.top().second);
            heap.pop();
        }

        return ans;
    }
};