[Programmers] 베스트앨범

• 문제
  

• 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare1(pair<int, string> a, pair<int, string> b){
	return a.first > b.first;
}
bool compare2(pair<int, int> a, pair<int, int> b){
	if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second > b.second;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, int> genreCount;
    unordered_map<string, vector<pair<int,int>>> map;
    
    //장르 순서 정하기
    for(int i=0;i<genres.size(); i++){
        string g = genres[i];
        genreCount[g]+= plays[i];  
        map[g].push_back(make_pair(i, plays[i]));
    }
    
    vector<pair<int, string>> v;
    for(auto i: genreCount){
        v.push_back(make_pair(i.second, i.first));
    }
    sort(v.begin(), v.end(), compare1);

    for(int i=0; i<v.size(); i++){
        string s = v[i].second;
        sort(map[s].begin(), map[s].end(),compare2);
        for(int j=0; j<2&&j<map[s].size(); j++){
            answer.push_back(map[s][j].first);
        }
    }
    
    return answer;
}

• 풀이

처음 알고리즘 풀기 시작할 때 Hash Map 알고리즘을 위주로 시작했었는데, 오랜만에 Hash Map 분류에 있는 문제를 도전했다.

처음에 unordered_map<string, int> genreCount 에 장르별로 재생된 횟수를 기록하고, 벡터에 담아 횟수 순으로 정렬해서 장르의 순서를 지정하였다.

그리고 장르 순서대로 해당 장르에 속하는 노래 리스트를 정렬하되, compare2로 연산자를 오버라이딩 하여, 정렬하고 최대 2개까지 answer벡터에 들어가도록 하였다.

다른 사람 풀이를 보니

while (fororder.size() > 0) {
       pair<int, string> temp= fororder.back();
       fororder.pop_back();
       
       ...
       } 

이런 식으로 vector를 다뤘는데, 이러면 내림차순으로 바꿀 필요도 없으니까 깔끔한 것 같다.