[LeetCode] 451. Sort Characters By Frequency

https://leetcode.com/problems/sort-characters-by-frequency/

Sort Characters By Frequency - LeetCode

Sort Characters By Frequency - Medium

 

 

String이 주어졌을때, 알파벳의 빈도가 높은 순서로 재배열하여 출력하는 문제이다.

hash map을 이용해 알파벳의 수를 받아준 후,

priority queue에 하나씩 넣어 뽑아주면 된다.

 

전체 풀이 코드

class Solution {
public:
    struct compare{
        bool operator()(pair<char, int> a, pair<char, int> b) {return a.second<b.second;}
    };
    string frequencySort(string s) {
        unordered_map<char, int> m;
        priority_queue<pair<char, int>, vector<pair<char,int>>, compare> pq;
        string ret;
        for (int i=0; i<s.size(); i++) m[s[i]]++;
        unordered_map<char, int>::iterator iter = m.begin();
        while(iter!=m.end()) pq.push(make_pair(iter->first, iter++->second));
        while (!pq.empty()) {
            pair<char, int> p = pq.top();
            for (int i=0; i<p.second;i++) ret+=p.first;
            pq.pop();
        }
        return ret;
    }
};