451. Sort Characters By Frequency - medium
문제
Given a string, sort it in decreasing order based on the frequency of characters.
제한사항
- 1 <= A.length = A[0].length <= 20
- 0 <= A[i][j] <= 1
입출력 예
1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input:
"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.
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
1
2
3
4
5
6
7
8
9
10
11
12
Example 3:
Input:
"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.
풀이
- Hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
string frequencySort(string s) {
string ans = "";
unordered_map<char, int>m;
vector<pair<int, char>> item;
// map을 통해 문자열내의 반복 문자의 횟수를 계산
for(auto& i : s)
++m[i];
// 정렬을 위해 vector에 저장
for(auto& i : m)
item.push_back({i.second, i.first});
// 내림차순으로 정렬
sort(item.begin(), item.end(), [](pair<int, char> &a, pair<int, char> &b){
return a.first > b.first;
});
// 많은 반복문자 순으로 문자열 구성
for(auto& i : item){
for(auto j = 0 ; j < i.first ; ++j)
ans.push_back(i.second);
}
return ans;
}
};