[백준 2910]빈도정렬]

문제

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

설계 

1. 수열의 길이와 요소의 최대값을 받는다. 

2. n회 반복하는 for문을 생성한다.

3. 요소를 하나씩 반복한다.

4. 요소의 횟수를 셀 수 있는 map을 생성한다.

5. key값을 요소의 값로 하고 value값을 요소의 개수로 처리한다. 

6. 하나의 map을 더 생성하여 요소값을 key 순서(포문의 인덱스 i +1)을 하여 value값을 만든다.(이 문제의 핵심)

7. 생성된 map을 그대로 vector에 집어 넣는다.

8. 넣은 vector를 정렬한다.

9. 정렬할 때 커스텀 cmp를 지정하여 지정한다.(이 문제의 핵심)
     9 -1. 커스텀 정렬에서는 같은 값이 존재할 때 인덱스 map에서 해당 요소 중 뭐가 먼저 나왔는지로 판단한다.
              커스텀 오퍼레이터를 만드는 이유는 그냥 변수끼리만 비교한다고 했을 때는 문제가 없다. 만약 구조체를 비교해야할 경우가 발생                  할 경우 각각의 요소를 비교해야하기 때문에 커스텀하게 만든다.

 

10. 그리고 v를 출력한다. 

 

코드

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

int a[1004];
map<ll,ll> _map;
map<ll, ll> order;
int c,n;
vector<pair<ll,ll>> result;

bool cmp(pair<ll,ll> a, pair<ll,ll> b){
    if(a.first == b.first){
        return order[a.second] < order[b.second]; // 왼쪽이 오른쪽보다 작다고 생각한다. 
    }
    return a.first > b.first; // 왼쪽이 오른쪽 보다 크다고 생각한다.
}
 
int main() {
    cin >> n >> c;

    for (int i = 0 ; i < n; i++) {
        cin >> a[i];
        _map[a[i]]++;
        if(order[a[i]] == 0) order[a[i]] = i + 1; // 인덱스는 0부터 시작하기 때문에
    }

    for(auto a : _map ) {
                        // 요소 개수 , 요소의 값
        result.push_back({a.second, a.first});
    }

    sort(result.begin(), result.end(), cmp);
    for (auto a : result) {
        for(int i = 0 ; i < a.first; i++){
            cout << a.second << " ";
        }
    }

}