C++에서 빈도로 문자 정렬

문자열이 있다고 가정하면 빈도에 따라 문자를 정렬해야 합니다. 따라서 문자열이 "abbbacbcc"와 같으면 출력은 "bbbbcccaa"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• v라는 쌍의 배열을 만들고 하나의 맵 m을 만듭니다.
• 문자열의 모든 문자에 대해,
  • m[character] 값을 1 증가
• i :=지도의 첫 번째 요소
• 지도에 요소가 있는 동안
  • v에 (i.second, i.first) 삽입
  • 다음 요소를 가리키도록 i를 늘립니다.
• 벡터 v 정렬
• ans :=빈 문자열
• for i :=0 ~ v
  • t :=v[i]의 첫 번째 요소
  • t가 0이 아닌 동안
    • ans :=ans + v[i]의 두 번째 부분
    • t 1 감소
• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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