C++에서 문자를 빈도순으로 정렬하는 방법

문자열이 주어졌을 때, 각 문자를 등장 빈도를 기준으로 내림차순 정렬하는 문제입니다. 예를 들어 입력 문자열이 "abbbacbcc"라면, b가 4번, c가 3번, a가 2번 등장하므로 출력은 "bbbbcccaa"가 됩니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

• (빈도, 문자) 쌍을 저장할 벡터 v와, 문자별 개수를 저장할 맵 m을 생성합니다.
• 문자열의 모든 문자를 순회하며 m[문자] 값을 1씩 증가시켜 각 문자의 빈도를 계산합니다.
• 맵의 첫 번째 요소부터 시작하여, 맵에 요소가 남아 있는 동안 다음을 반복합니다.
  • (빈도, 문자) 형태의 쌍을 벡터 v에 삽입합니다.
  • 반복자를 다음 요소로 이동시킵니다.
• 벡터 v를 빈도 기준으로 정렬합니다.
• 정답 문자열 ans를 빈 문자열로 초기화합니다.
• 벡터 v의 각 요소에 대해 해당 빈도만큼 문자를 ans에 반복해서 추가합니다.
• 최종적으로 ans를 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(pair <int, char> a, pair <int, char> b){
        return a.first < b.first;
    }
    string frequencySort(string s) {
        vector < pair <int, char> > v;
        map <char, int> m;
        for(int i = 0; i < s.size(); i++){
            m[s[i]]++;
        }
        map <char, int> :: iterator i = m.begin();
        while(i != m.end()){
            v.push_back({i->second, i->first});
            i++;
        }
        sort(v.rbegin(), v.rend(), cmp);
        string ans = "";
        for(int i = 0; i < v.size(); i++){
            int t = v[i].first;
            while(t--)ans += v[i].second;
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.frequencySort("abbbacbcc");
}

입력

"abbbacbcc"

출력

bbbbcccaa

코드 설명

먼저 map<char, int>를 사용해 각 문자의 등장 횟수를 집계합니다. 그다음 맵을 순회하면서 (빈도, 문자) 형태의 pair를 벡터에 담고, sort(v.rbegin(), v.rend(), cmp)를 호출해 빈도가 높은 문자부터 앞에 오도록 역방향 정렬합니다. 마지막으로 정렬된 벡터를 순회하며 각 문자를 빈도만큼 반복해 결과 문자열을 만들면 됩니다.

이 알고리즘의 시간 복잡도는 문자 개수를 n이라 할 때 O(n log n)이며, 공간 복잡도는 O(n)입니다. 해시 맵(unordered_map)을 사용하면 평균적으로 더 빠른 성능을 얻을 수 있습니다.