[LeetCode] 451. Sort Characters By Frequency

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Sort Characters By Frequency

문제 유형 : 문자열 처리, 해시, 정렬, 우선순위 큐

문제 난이도 : Medium

 

문제

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 

문자열 s가 주어진다. 문자의 등장 횟수에 따서 내림차순으로 정렬하라.

정렬된 문자열을 반환하라. 여러 답이 있을 수 있는데, 하나만 반환하면 된다.

 

풀이

우선, 순차적으로 문자열을 순회하면서 문자별로 개수를 파악한다.

해시맵을 이용하면 된다.

 

이후 두 가지 방법으로 나뉜다:

key-value를 우선순위 큐에 넣었다가 빼면서 각각 key*value만큼 빈 문자열에 붙이는 방법과,

사용자 지정 정렬을 이용해서 문자열을 정렬하는 방법이 있다.

사용자 지정 정렬에서 주의할 점은, 개수가 같을 때의 처리를 해줘야한다는 거다.

ex) olol이 정렬되지 않는다. ooll 또는 lloo로 정렬되어야 한다.

 

코드

C++ - 우선순위 큐를 이용한 풀이

struct comp {
    bool operator()(const auto &a, const auto &b) {
        return a.second < b.second;
    }
};

class Solution {
public:
    string frequencySort(string s) {
        priority_queue<pair<char, int>, vector<pair<char, int>>, comp> pq;
        unordered_map<char, int> mp;

        for(const char &ch : s) {
            mp[ch]++;
        }

        for(const auto &entry : mp) {
            pq.push({entry.first, entry.second});
        }

        string res = "";
        while(!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            res.append(p.second, p.first);
        }

        return res;
    }
};

 

 

Go - 사용자 지정 정렬을 이용한 풀이

var mp map[rune]int

type ByFreq []rune

func (b ByFreq) Len() int           { return len(b) }
func (b ByFreq) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }
func (b ByFreq) Less(i, j int) bool { 
    if mp[b[i]] == mp[b[j]] {return b[i] < b[j]}
    return mp[b[i]] > mp[b[j]] 
}

func frequencySort(s string) string {
	mp = make(map[rune]int)

	for i := 0; i < len(s); i++ {
		mp[rune(s[i])]++
	}

	res := []rune(s)
	sort.Sort(ByFreq(res))

	return string(res)
}