[구현 / BOJ 2910 / C++] 빈도 정렬

https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

1) 빈도수를 저장해야하므로 맵 자료구조를 사용한다. 이때, 맵 자료구조를 하나 더 사용하여 나온 순서도 저장한다.
2) 저장된 맵 자료구조를 정렬해야하므로 vector에 저장해준다.
3) 빈도수 정렬의 규칙에 따라 cmp 함수를 설정하고 sort를 진행한다.
4) vector를 출력한다. 

 우선 해당 수 : 빈도 수 가 필요하다는 것은 바로 알아차렸을 것이다. 그렇다면 바로 써줘야하는 자료구조는 바로 map이다!!!

map을 이용하면 매우 간단하게 해당수 : 빈도 수를 저장할 수 있다.

 

m1[해당수]++ 처럼 쓰면 map의 key는 해당수로 설정되고, value는 자동으로 ++를 진행한다.

 

그리고 정렬을 해야하므로 sort가 필요하다. map은 sort가 불가하므로 vector에 저장해준다.

 

이제 sort에 들어갈 세 번째 인수 cmp 함수가 매우 중요하다!! 먼저 빈도수는 저장했으니 

map이나 vector를 이용해 빈도수를 비교한다!!

 

이제 나온 순서를 알아야한다. 안타깝게도 맵 자료구조 한개로는 나온 순서를 저장할 수 없다.. 따라서 해당 숫자 : 나온 순서 를 저장해주는 map을 만들어주자!

 

나머지는 코드의 흐름을 읽어보면 알 수 있을 것이다!!

 

이 문제의 핵심은 map 자료구조를 쓰는 것, 정렬할 때 sort를 사용하고 cmp를 설정하는 것이겠다.

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

int N, C, tmp;
map<int, int> m1, m2; // 해당 수 : 빈도수
vector<pair<int, int>> v; // 정렬용

bool cmp(pair<int, int> a, pair<int, int> b){
    if(m1[a.X] == m1[b.X]) return m2[a.X] < m2[b.X]; // 빈도수 같다면 나온순서
    return m1[a.X] > m1[b.X]; // 우선 빈도수 큰 순서
    
    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> C;
    for(int i = 0 ; i < N ; i++){
        cin >> tmp; m1[tmp]++; // 빈도수 증가
        if(m2[tmp]==0) m2[tmp] = i+1; // 숫자 나온 순서
    }
    
    for(auto a : m1) v.push_back({a.X, a.Y}); // 해당 숫자 : 빈도수
    
    
    sort(v.begin(), v.end(), cmp);
    
    for(auto a : v)
        while(a.Y--) cout << a.X << ' ';
    
}