백준 2910 빈도정렬 // 커스텀정렬, 인덱스에 의미부여

2910번: 빈도 정렬 (acmicpc.net)

2910번: 빈도 정렬

* 인덱스에 의미를 부여하라!

ex)mp[2] ==2의 빈도

 

mp(해당숫자,빈도)

mp_first(해당숫자,최초등장순서)

v(빈도,해당숫자)

 

*빈도수(v.first)만큼 출력해야함에 주의

ex) (0,0) (2,1) (3,2) 일때, 0은 출력안됨, 1 1 2 2 2 출력.

for (auto i : v) {
        for (int j = 0; j < i.first; j++) 
        {
            //빈도수만큼 출력해야함!!
            cout << i.second << " ";
        }
    }

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n, c, a[1004];
map<int, int> mp,mp_first;  //빈도저장,등장순서저장
vector<pair<int, int>> v;   //<빈도,key>

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first)
        return mp_first[a.second] < mp_first[b.second];
    return a.first > b.first;
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL); cout.tie(NULL);
    cin >> n>>c;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        mp[a[i]]++; //인덱스==키, 값==해당키의 빈도수
        if (mp_first[a[i]] == 0) mp_first[a[i]] = i+1;
        //첫등장이면, 등장순서 저장

       // v.push_back({ mp[a[i]] ,a[i] });
    }
    for (auto it : mp) {
        v.push_back({ it.second, it.first });
    }
    sort(v.begin(), v.end(), cmp);
    for (auto i : v) {
        for (int j = 0; j < i.first; j++) 
        {
            //빈도수만큼 출력해야함!!
            cout << i.second << " ";
        }
    }
    
    
    return 0;
}