[programmers][해시] 베스트앨범 : https://programmers.co.kr/learn/courses/30/lessons/42579#

베스트앨범.cpp

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool compare(pair<int,int>& a, pair<int,int>& b){
    // 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
    if(a.first == b.first){
        return a.second < b.second;        
    }
    // 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    
    int size = genres.size();
    // <genres, songs<play,index>>
    map<string, vector<pair<int,int>>> songMap;
    // <genres, count>
    map<string, int> cntMap;
    
    // input
    for(int i=0; i<size; i++){
        string genre = genres[i];
        int play = plays[i];
        
        songMap[genre].push_back({play, i});
        cntMap[genre]+=play;
    }
    
    // cntMap's reverse map
    // <count, genres>
    map<int, string> rcntMap;
    for(map<string, int>::iterator it = cntMap.begin(); it != cntMap.end(); it++){
        rcntMap[it->second] = it->first;
    }
    
    vector<int> answer;
    
    // 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
    for(map<int, string>::reverse_iterator it = rcntMap.rbegin(); it != rcntMap.rend(); it++){
        vector<pair<int,int>> songs = songMap[it->second];
        
        sort(songs.begin(), songs.end(), compare);
        for(int i=0; i < min(2, (int)songs.size()) ;i++){
            answer.push_back(songs[i].second);
        }
    }
    
    return answer;
}