Sort Characters By Frequency(Hash Table,String,Sorting,Heap (Priority Queue),Bucket Sort,Counting)

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

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.

 

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

• 1 <= s.length <= 5 * 105
• s consists of uppercase and lowercase English letters and digits.

1. Python

뭐.. 좀 무식하긴하지만 어찌어찌 풀어는 냈다 ㅋㅋ

class Solution:
    def frequencySort(self, s: str) -> str:
        dic = {}
        for ch in s :
            if ch not in dic :
                dic[ch] = 1
            else : dic[ch]+=1
        ans = ""
        while dic:
            temp = 0
            ch = ''
            for alpha,freq in dic.items():
                if freq > temp :
                    temp = freq
                    ch = alpha
            dic.pop(ch)
            ans += ch*temp
        return ans

그닥 달갑진 않은 스코어 ㄷㄷ..

얍실하게 Counter를 써서 풀어도 된다고 한다..

class Solution:
    def frequencySort(self, s: str) -> str:
        freq=Counter(s)
        sor_char=sorted(freq.items(), key=lambda item : item[1], reverse=True)
        result=''.join(char*count for char,count in sor_char)
        return result

 

2. C

C에선 qsort를 이용하라는데, 솔직히 잘 모르겄당

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 문자 빈도를 저장할 구조체
typedef struct {
    char ch;   // 문자
    int freq;  // 빈도
} CharFreq;

// 비교 함수 (빈도 내림차순, 빈도가 같으면 문자 기준 오름차순)
int compare(const void *a, const void *b) {
    CharFreq *x = (CharFreq *)a;
    CharFreq *y = (CharFreq *)b;
    if (y->freq != x->freq) {
        return y->freq - x->freq; // 빈도 내림차순
    }
    return x->ch - y->ch; // 문자 오름차순
}

char *frequencySort(char *s) {
    int freq[128] = {0}; // ASCII 문자 빈도 계산

    // 빈도 계산
    for (int i = 0; s[i] != '\0'; i++) {
        freq[(int)s[i]]++;
    }

    // 빈도가 있는 문자들로 CharFreq 배열 생성
    CharFreq charFreqs[128];
    int count = 0; // 실제 문자의 개수
    for (int i = 0; i < 128; i++) {
        if (freq[i] > 0) {
            charFreqs[count].ch = (char)i;
            charFreqs[count].freq = freq[i];
            count++;
        }
    }

    // CharFreq 배열 정렬
    qsort(charFreqs, count, sizeof(CharFreq), compare);

    // 결과 문자열 생성
    int len = strlen(s);
    char *result = (char *)malloc((len + 1) * sizeof(char));
    int idx = 0;

    for (int i = 0; i < count; i++) {
        for (int j = 0; j < charFreqs[i].freq; j++) {
            result[idx++] = charFreqs[i].ch;
        }
    }
    result[idx] = '\0'; // NULL 문자로 끝내기

    return result;
}

 

3. C++

C++은 요런 느낌으로 하면 된다.

신기한 것은

 

map을 정의해놨다면, vector<pair<char,int>> vec(map.begin(),map.end()) 요렇게 쉽게 map에 있는 것을 따와서 vector를 initialize할 수 있다.

 

그리고, vec을 그 안 성분 pair 기준으로 정렬을 할 때. pair의 second 기준으로 정렬을 하고 싶다면

sort(vec.begin(),vec.end(),[ ](pair<char,int> &a, pair<char,int> &b){ return a.second > b.second}); => 오름차순

 

이렇게 할 수 있다.

 

그리고 string에 char을 더해 줄 때, string str이라고 하면, str.append(5,'a') 이러면 str에 'a'를 5만큼 더하라는 뜻이 된다.

 

나머지는 아래 코드 참고

 

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    string s = "APPLETREE";
    unordered_map<char,int> m;
    for(char ch : s){
        m[ch]++;
    }

    // for(const auto p : m){
    //     cout<<p.first<<" "<<p.second<<endl;
    // }

    vector<pair<char,int>> vec(m.begin(),m.end());

    sort(vec.begin(),vec.end());
    // for(const auto x : vec){
    //     cout<<x.first<<" "<<x.second<<endl;
    // } // 일반 정렬 --> 효과 없음
    sort(vec.begin(),vec.end(),[](pair<char,int> &a,pair<char,int> &b){
        return a.second > b.second;
    });
    // for(const auto x : vec){
    //     cout<<x.first<<" "<<x.second<<endl;
    // }
    string ans;
    for(auto p : vec){
        ans.append(p.second,p.first);
    }
    cout << ans;
}