[백준 2910번] 빈도 정렬 (C++)

문제링크 : https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, C;

map<int, int> m;
map<int, int> idx;

bool comp(const pii& a, const pii& b)
{
    if(a.second == b.second) return idx[a.first] < idx[b.first]; //크기가 같은 경우, 인덱스로 구분
    return a.second > b.second;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> C;
    for(int i=1; i<=N; i++)
    {
        int num;
        cin >> num;
        m[num]++;
        
        if(!idx[num])
        { 
            idx[num] = i;
        }
    }

    vector <pii> v(m.begin(), m.end()); //key, value(값, 갯수)
    sort(v.begin(), v.end(), comp);

    for(int i=0; i<v.size(); i++)
    {
        for(int j=0; j<v[i].second; j++)
        {
            cout <<v[i].first << " ";
        }
    }
    
}

맵을 활용하여 푼 문제다.

먼저 숫자를 입력받고 해당 숫자를 key로 입력받을 때마다 해당 key의 value 값을 증가시켜준다.

그리고 index도 따른 맵에 같이 저장해준다.

이때 해당 key값이 없을 때만 index 값 i를 저장해주도록 하여 중복을 방지한다.

 

이후 정렬을 해주는데 따로 정렬 조건을 만들어준다.

각 key에 대한 사이즈 즉 value 값을 기준으로 클 수록 앞에 온다.

하지만 value 값이 같을 때도 있는데 이때는 따로 저장해줬던 index를 기준으로 index값이 작으면 앞에 오도록 한다.