[프로그래머스 Level_3 / C++] 베스트앨범

unordered_map 을 활용해서 정렬을 잘할 수 있는지를 묻는 문제이다. 

 

#접근방법 

1. map(장르, 재생횟수, 고유번호) m1 생성
2. map (장르, 재생횟수 합) m2 생성
3. m2에 합산한 값 저장한 후 내림차순으로 정렬 
4. m1에 재생횟수의 내림차순으로 정렬하며 재생횟수가 같으면 고유번호 오름차순으로 정렬
5. m2의 Key 값은 장르의 이름이며 재생횟수의 합이 큰 것부터 작은 것까지 정렬되어있다. 그러므도 m1에서 m2 장르의 이름을 key값으로 가지는 것을 차례대로 보면서 정렬되어있는 고유번호를 2개까지만 answer에 저장하면된다. 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(pair<int,int>v1, pair<int,int>v2){
    if(v1.first==v2.first) return v1.second<v2.second;
    //재생횟수 같으면 고유번호 오름차순
    else return v1.first>v2.first; 
    //재생횟수 내림차순
}

bool cmp1(pair<string, int> v1, pair<string, int> v2){
    return v1.second>v2.second;
    // 장르 재생횟수 합 내림차순
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map <string,vector<pair<int,int>>> m1; //장르,재생횟수,고유번호
    unordered_map <string, int> m2; // 장르별 재생횟수 합     
    for(int i=0; i<genres.size(); i++){
        m1[genres[i]].push_back({plays[i], i}); 
        m2[genres[i]]+=plays[i]; 
    }    
    for(auto &x : m1){
        sort(x.second.begin(), x.second.end(), cmp); 
    }    
    vector <pair<string, int>> v(m2.begin(),m2.end()); 
    sort(v.begin(),v.end(),cmp1);     
    for(auto x : v){
        for(int j=0; j<m1[x.first].size(); j++){
            answer.push_back(m1[x.first][j].second); 
            if(j)break; 
        }        
    }
    return answer;
}

코딩테스트 연습 - 베스트앨범