프로그래머스 - 베스트앨범

프로그래머스 - 베스트앨범

map과 sort정도만 이용하면 금방 풀 수 있는 문제인 것 같다.

추가적으로 key로 genres 값인 string을 사용하는데, 이들의 정렬성은 필요없다.
그래서 unordered_map을 사용했는데, 데이터셋이 크지 않아서 map을 쓸때와 큰 속도차이는 없는 것 같다.

코드는 아래와 같다.

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

using namespace std;
#define pii pair<int, int>
/*map<string, int> m;
map<string, vector<pii>> m1;*/
unordered_map<string, int> m;
unordered_map<string, vector<pii>> m1;
bool compare(const pii &a, const pii &b)
{
    if(a.first == b.first) 
        return a.second < b.second;
    
    return a.first > b.first;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    int size = genres.size();
    
    for(int i=0;i<size;i++) {
        m[genres[i]] += plays[i];
        m1[genres[i]].push_back( { plays[i], i } );
    }
    
    vector<pair<int, string>> v;
    for(auto it : m) 
        v.push_back( { it.second, it.first} );
    
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    
    for(auto it : v) {
        vector<pii> v1 = m1[it.second];
        sort(v1.begin(), v1.end(), compare);
        int cnt = 0;
        for(auto itt : v1) {
            answer.push_back(itt.second);
            cnt++;
            if(cnt == 2)
                break;
        }
    }
    
    return answer;
}