C++에서 Map을 value 기반으로 정렬하기

Map 의 기본 정렬 상태

 map은 key값을 기준으로 오름차순 정렬되어 있습니다.

 

만일 key값 내림차순으로 변경하기 위해서는 다음의 3번째 인자를 활용해야 합니다.

// 키, 데이터, compare
map<int, int, greater<int>> m;

 

Value 기반 정렬하기

map은 tree 형태로 되어 있고, tree 형태를 만드는 과정에서 key를 기준으로 정렬합니다.
완성된 tree를 재정렬하는 sort() 함수는 존재하지 않습니다.
pair 기반의 vector에 map이 가지고 있는 pair를 모두 넣고 정렬하면 value 기준 정렬이 가능해집니다.

 

 

다음의 두 단계로 진행됩니다. 

1. map을 vector로 이동
2. vector를 second 기준으로 정렬

1. map 을 vector로 이동

 

2. value 기준 비교 함수 cmp

pair를 인자로 전달 받아, 두번 째 값을 비교하는 사용자 정의 함수를 활용해 두 값을 비교합니다.

bool cmp(coinst pair<int, int>& a, const pair<int, int>& b){
    if(a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

 

vector의 second 기준으로 정렬

map의 key value가 <int, int> 일 때

sort(vec.begin(), vec.end(), cmp);

 

Value 기반 정렬 활용

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

 

아래 코드는 수열이 주어졌을 때, 빈도 정렬 프로그램입니다.

#include <bits/stdc++.h>
#define pp pair<int, int>
using namespace std;

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

bool cmp(pp a, pp 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;
}

 

참조: https://www.geeksforgeeks.org/sorting-a-map-by-value-in-c-stl/

Sorting a Map by value in C++ STL - GeeksforGeeks