[LeetCode C++] 692. Top K Frequent Words

⭐️ 난이도

Medium

---

⭐️ 문제

https://leetcode.com/problems/top-k-frequent-words/

Top K Frequent Words - LeetCode

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

 

string 배열인 words와 정수 k가 주어졌을 때, 가장 많이 쓰인 string k개를 구하시오.

빈도가 높은 순서대로 답을 구하되, 만일 같은 빈도로 쓰인 단어가 있다면 사전적 순서로 정렬하시오.

 

---

⭐️ Follow-up

Could you solve it in O(n log(k)) time and O(n) extra space?

---

⭐️ Idea flow

1. 단어들이 몇 번씩 쓰였는지 확인 필요.
   Follow-up에서 time complexcity를 만족시키려면 어떻게 해야 할까?

   sort 이후 lower_bound, upper_bound 이용하면 어떨까?

   둘 다 시간 복잡도가 전체 원소 개수의 로그에 비례한다. 즉, O(log (last - first))이다.

   이 방법을 적용시키면 정확히 시간 복잡도가 어떻게 되는지는 모르겠지만 나쁘지 않을 것이라는 생각이 들었다.

 

   따라서 words를 정렬 한 후에, upper_bound - lower_bound를 하면 해당 단어가 몇 개 있는지 구할 수 있을 것이다!

   해당 단어의 빈도를 구했으면 해당 단어가 몇 번 나왔는지 더 구할 필요가 없으므로, 다음 검사 시 범위를 더 좁힌다.

 

2. Heap의 시간 복잡도는 O(n logn)이다.

    C++의 경우 priority_queue가 heap을 기반으로 하고 있다.

    마침 빈도가 높은 순으로, 다음으로 사전 순으로 결과 값을 반환해야 하므로 priority_queue<pair<int, string>>을 이용하면 될 것이다.

    lower&upper_bound를 이용해 얻은 값을 priority_queue에 넣으면 될 것이다.

    또한 아래와 같이 사용자 정의 비교 함수를 통해 내가 원하는대로 정렬이 가능하다.

    struct compare{
        bool operator()(pair<int, string> &a, pair<int, string> &b){
            if(a.first == b.first){ // 빈도가 같을 때에는 string 사전순으로
                return a.second > b.second;
            }
            else{ // 빈도가 다를 때에는 빈도순으로
                return a.first < b.first;
            }
        }
    };

 

3. priority_queue에서 k개만큼 원소를 꺼내기

   각 단어가 몇 번 나왔는지 구해서 priority_queue에 넣었으니, 이제 k개만큼 원소를 꺼내면 된다.

 

---

⭐️ Code

class Solution {
public:
    struct compare{
        bool operator()(pair<int, string> &a, pair<int, string> &b){
            if(a.first == b.first){ // 빈도가 같을 때에는 string 사전순으로
                return a.second > b.second;
            }
            else{ // 빈도가 다를 때에는 빈도순으로
                return a.first < b.first;
            }
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> result;
        priority_queue<pair<int, string>, vector<pair<int, string>>, compare> pq; // first:frequency, second: word
        sort(words.begin(), words.end());

        for(int i = 0; i < words.size();){
            string tmp = words[i];
            auto iter_upper = upper_bound(words.begin() + i, words.end(), tmp);
            auto iter_lower = lower_bound(words.begin() + i, words.end(), tmp);

            int count = iter_upper - iter_lower;
            i += count;
            pq.push(make_pair(count, tmp));
        }

        for(int i = 0; i < k; i++){
            result.push_back(pq.top().second);
            //result.insert(result.begin() + i, pq.top().second);
            //result.emplace_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
};

---

⭐️ Feedback

Discuss에 들어가서 다른 사람의 코드를 확인해보았다.

 

거의 모든 사람들이 priority_queue를 사용했다. 그런데 여기에 unordered_map을 사용하는 코드를 많이 볼 수 있었다.

원래 map과 multimap은 알고 있었는데, unordered_map은 처음 들었다.

 

unordered_map이란 무엇일까?

unordered_map은 map과는 다르게 <key, value>형태의 pair 객체를 원소로 갖고 있지만, key를 정렬된 상태로 저장하지 않는다. 말 그대로 unordered(정렬되지 않은) 상태인 것이다. 

map은 binary search tree 기반인 반면, unordered_map은 hash table을 기반으로 한다.

따라서 탐색 시간 복잡도가 O(1)로 보장이 된다.

sorting이 필요 없을 때, unordered_map을 사용하면 더 빠른 탐색이 가능하다는 것이다!

 

그럼 이것을 어떻게 사용할까?

map과 마찬가지로 key가 유일해야 하기 때문에, key를 string으로, value를 int로 사용한다. (unordered_map<string, int>)

그리고 words 배열을 돌면서 해당 단어(key)가 나올 때마다, value를 1씩 올려준다.

이렇게 하면 해당 단어가 몇 번 나왔는지 value를 통해 알 수 있다.

 

그리고 unordered_map의 모든 원소를 돌면서 priority_queue에 넣고 이후에는 내가 한 과정과 거의 유사했다.

 

[전체 코드 보기]

vector<string> topKFrequent(vector<string>& words, int k) {
    vector<string> result;
    unordered_map<string, int> hashmap;
    priority_queue<pair<int, string>, vector<pair<int, string>>, compare> pq;

    for(string& words: words){
        hashmap[words] += 1;
    }

    for(auto iter = hashmap.begin(); iter != hashmap.end(); iter++){
        pq.push(make_pair(iter->second, iter->first));
    }

    for(int i = 0; i < k; i++){
        //result.insert(result.begin(), pq.top().second);
        //result.emplace_back(pq.top().second);
        result.insert(result.begin() + i, pq.top().second);
        pq.pop();
    }

    return result;
}

 

####Point!

unordered_map 컨테이너는 hash table 기반이며 탐색 시간 복잡도가 O(1)로 매우 빠르다.

대신 key가 sorting되어 있지 않다.

 

 

leet code를 시작한지 1일차이다.

아직 백준 문제들을 풀어보면서 시간 복잡도에 대해서 어느정도 감은 잡힌 상태이지만, 지금 내가 짠 코드가 정확히 어느정도 시간 복잡도를 가지고 있는지 잘 모르겠다.

앞으로 꾸준히 문제를 풀면서 내 풀이와 다른 사람의 풀이, 그리고 C++에 대해서 더 공부하면 더 효율적이고 좋은 코드를 짤 수 있을 것 이라고 믿는다!