본인 풀이

#include<bits/stdc++.h>
using namespace std;
int n, c;
int a[1000];
vector<int> ret;

// 숫자: <첫 인덱스, 빈도수>
map<int, pair<int, int>> mp;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> c;

    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    for (int i = 0; i < n; i++){
        if(mp[a[i]].second){
            mp[a[i]].second++;
        }else{
            mp[a[i]].first = i;
            mp[a[i]].second = 1;
        }
    }

    while (ret.size() < n)
    {
        // 1. 빈도수 max값 출력
        int mx = 0;
        vector<int> mx_keys;
        for (auto it : mp)
        {
            mx = max(it.second.second, mx);
        }

        // 2. 빈도수 max값을 가지는 모든 요소 리턴
        // 키값만 추출해서 벡터에 일단 pair 인덱스값과 함께 보관
        vector<int> idx;
        for (auto it : mp)
        {
            if (it.second.second == mx)
            {
                // 숫자 1 : 등장인덱스, 등장횟수
                // 인덱스에 직접 접근하면 해당 숫자가 나오니까, ret에 해당 빈도수만큼 Push
                // 우선 정렬해야하니 int 벡터에 푸시
                idx.push_back(it.second.first);
                mx_keys.push_back(it.first);
            }
        }

        // 3. 먼저 등장하는 요소들을 출력하기 위해 오름차순 출력
        sort(idx.begin(), idx.end());

        // 4. 푸시
        for (int i : idx)
        {
            // 등장횟수만큼 푸시
            for (int j = 0; j < mx; j++)
            {
                ret.push_back(a[i]);
            }
        }

        // 5. mx에 해당하는 map의 키값 삭제
        for (int i : mx_keys)
        {
            mp.erase(i);
        }
    }
    for(int i: ret){
        cout << i << " ";
    }
    cout << "\n";
    return 0;
}

1. map을 통해 각 숫자별 빈도수를 측정
2. 정답으로 제출할 벡터 크기가 제시된 n사이즈와 동일해질때까지 while문 내의 로직을 돌렸음.
3. 빈도수들 중 최댓값을 mx변수에 담아 측정
4. 다시한번 맵 전체를 순회하며 mx값과 동일한 빈도수를 갖는 대상을 추출. 이때 맵의 value값은 pair<해당 숫자가 처음 등장한 곳의 인덱스, 등장횟수> 로 이루어진다.
5. mx_keys에 최댓값 빈도수 숫자들의 맵 키값들을 푸시해둔다. 해당 키들은 마지막에 erase하여 순회시에 효율을 더하기 위함
6. 등장 인덱스 벡터를 오름차순 정렬하여 처음 등장한 대상먼저 출력하도록 설정
7. pair의 second에 있는 등장 횟수만큼 ret에 푸시
8. map에서 사용한 key는 erase하고 로직 다시 시작

모범 답안

#include<bits/stdc++.h>
using namespace std;

int n, c, a[1004];
vector<pair<int,int>> v;
map<int, int> mp, mp_first;

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(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> c;
    // mp은 등장횟수
    // mp_first는 첫 등장 인덱스
    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;
        }
    }

    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;
}

1. sort의 3번째 파라미터는 정렬 기준을 담는 커스텀 오퍼레이터 함수를 넣을 수 있다. 비교기준이 둘 이상인 경우에 사용해도 좋을 것 같다.