C++에서 빈도별 요소 정렬 (Map vs Bucket 접근법)

Source: Dev.to

Problem Idea

주어진 배열에서 요소들을 빈도수 내림차순으로 정렬하고, 가장 빈번하게 등장하는 요소가 먼저 나오도록 배열을 재구성합니다.

Example
Input: [1,1,2,2,2,3]
Output: [2,2,2,1,1,3]

Approach 1: unordered_map + Sorting

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};
    unordered_map<int,int> freq;
    vector<int> res;

    for (int x : v) freq[x]++;

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

    sort(vec.begin(), vec.end(),
         [](auto &a, auto &b){ return a.second > b.second; });

    for (auto &p : vec) {
        for (int i = 0; i 

Time & Space Complexity

• Frequency count: O(n)
• Sorting: O(m log m) (여기서 m은 서로 다른 요소의 개수)
• Reconstruction: O(n)

Total time: O(n + m log m)
Space: O(m) (맵과 pair 벡터를 위한 공간)

Approach 2: Bucket (Counting Sort)

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};

    const int MAX = 100;               // maximum possible value (adjust as needed)
    vector<int> freq(MAX, 0);

    for (int x : v) freq[x]++;

    int maxFreq = 0;
    for (int f : freq) maxFreq = max(maxFreq, f);

    vector<vector<int>> bucket(maxFreq + 1);
    for (int i = 0; i < (int)freq.size(); ++i) {
        if (freq[i] > 0)
            bucket[freq[i]].push_back(i);
    }

    vector<int> res;
    for (int f = maxFreq; f > 0; f--) {
        for (int val : bucket[f]) {
            for (int i = 0; i < f; i++)
                res.push_back(val);
        }
    }

    for (int x : res) cout << x << " ";
}

Time & Space Complexity

• Frequency count: O(n)
• Bucket traversal & reconstruction: O(n)

Total time: O(n)

• Frequency array: O(k)
• Buckets: O(k)
• Result vector: O(n)

Total space: O(n + k)

What I Learned

• 정렬이 항상 필요한 것은 아니며, 버킷을 이용한 저장으로 간단한 인덱싱만으로 정렬을 대체할 수 있습니다.
• Big‑O 표기법에서는 상수 계수를 무시합니다 (O(2k) → O(k)).
• unordered_map은 유연하지만, 값의 범위가 알려져 있을 때는 고정 크기의 빈도 배열이 더 빠릅니다.

Practice Challenge

• 정렬 없이 unordered_map만 사용해 문제를 다시 풀어보세요.
• unordered_map 기반 빈도 테이블에 버킷 아이디어를 적용해 보세요.