Leetcode - 692. Top K Frequent Words

문제

주어진 문자열 중, 동일한 문자열의 빈도수가 많은 문자 순서대로 k개를 리턴하라. (단 문자열은 사전순 정렬되어있어야 한다)

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]

해결

unordered_map으로 빈도수를 저장하고. 저장된 값들을 priority_queue에 push한다. 그리고 heap구조에서 k개만 추출하면 된다. 비교 operater를 추가 인자로 전달하는 priority_queue 사용법을 익힐것!

이걸 C로 풀었다면 hashtable을 구현하고 heap을 구현했어야했는데, 이럴땐 STL이 참 은혜롭다..

이 문제를 해결함 으로써 드디어 Leetcode 에서 첫 Badge를 획득했다. LeetCode 75 라는 2주일간 총 30문제를 푸는 스터디 플랜이다. 2주동안 매일같이 Easy또는 Midium을 풀었는데 끝까지 해내서 기쁘다. 내일부터는 Weekly Contest도 참가해볼 예정!

class myCompare {
public:
    bool operator() (const pair<string, int> &p1, const pair<string, int> &p2) {
        if (p1.second == p2.second)
            return p1.first > p2.first;
        return p1.second < p2.second;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        /* generate hash map */
        unordered_map<string, int> freq;
        for (string w: words)
            freq[w]++;
        
        /* push string and freq value to heap */
        priority_queue<pair<string, int>, vector<pair<string, int> >, myCompare> pq;
        for (auto it: freq)
            pq.push(make_pair(it.first, it.second));
            //pq.push({it.first, it.second}); // make_pair()와 동일한 코드     
            
        /* pop k times */
        vector<string> ret;
        //for (int i = 0; i < k; i++) {  // 아래 코드가 더 간결
        while (k--) {        
            ret.push_back(pq.top().first);
            pq.pop();
        }
        return ret;
    }
};