2910 : 빈도 정렬 - map, 카운팅, 정렬

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

2910번: 빈도 정렬

---

문제요약

두 가지 조건에 맞게 정렬하여 출력

 

난이도

Silver 3

---

풀이 포인트

• 조건 파악
  • 1순위 : 빈도가 높을 수록 먼저
  • 2순위: 먼저 입력받은 값일 수록 먼저
• 적절한 자료구조 활용
  • map<key,value>
  • pair<int, int>;
• sort(v.begin(), v.end(), 비교함수);

bool compare(int a, int b) {
    return a > b; // 내림차순 정렬
}

vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
sort(vec.begin(), vec.end(), compare);

---

REVIEW

 

아직 map 사용이 미숙한지라 어떻게든 2차원 배열을 이용해서 풀어보려 했다.

2순위 조건, 등장한 빈도가 같을 때, 먼저 입력받은 값을 먼저 출력한다는 것을 구현하기가 어려웠다.

 

2차원 배열을 사용하든 map을 사용하든 key값에 따라 오름차순 정렬이 되어버리기 때문에 자꾸 순차적으로 출력되어버렸다.

• map<값, 갯수> : 값의 개수를 카운팅 해주는 map 하나
• map<값, 입력배열에서 그 값의 인덱스>: 입력배열에서 그 값의 위치를 저장하는 map하나

두 가지 map을 사용해 조건에 맞게 정렬해주어야 한다.

 

참 간단해 보이는데, 막상 구현하려니 꼬이고 꼬여서 스스로 바보임을 느낀 문제.

---

CODE

#include <bits/stdc++.h>
using namespace std;
//카운팅 하나, custom operator

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()
{
    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;
    }

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