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

프로그래머스

 

• 해시 문제라 unordered_map으로 접근
• 해당 unorded_map을 벡터에 할당해주고 벡터를 장르별 총합 재생수 기준으로 정렬해준 뒤 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬(뭐부터 정렬할지 순서는 상관없음)
• 이후 총합 재생수가 높은 장르부터 재생수가 높은 곡 2개를 수록. 단, 장르에 곡이 하나면 한 곡만 수록

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

// 장르 내의 곡들의 재생수 합이 가장 큰 장르부터 장르 내의 곡들을 재생수 순서대로 출력
// 가장 많이 재생된 노래를 두 개씩 모아서 재생
// 해시 문제 unordered_map 사용(key, value 삽입 시 정렬이 필요 없음)

using namespace std;

// 장르별 총합 재생 수 비교자
bool cmpGenre(const pair<string, pair<int, vector<pair<int, int>>>> &a, const pair<string, pair<int, vector<pair<int, int>>>> &b) {
    return a.second.first > b.second.first;
}

// 곡 재생 수 비교자
bool cmpPlay(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, pair<int, vector<pair<int, int>>>> m;
    vector<pair<string, pair<int, vector<pair<int, int>>>>> v;
    
    for(int i = 0; i < genres.size(); i++) {
        m[genres[i]].first += plays[i];
        m[genres[i]].second.push_back({i, plays[i]}); 
    }
    
    v.assign(m.begin(), m.end());
    
    // 장르별 총합 재생수 기준으로 정렬
    sort(v.begin(), v.end(), cmpGenre);
    
    // 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬
    for(int i = 0; i < v.size(); i++)
        sort(v[i].second.second.begin(), v[i].second.second.end(), cmpPlay);
    
    // 총합 재생수가 높은 장르마다 재생수가 높은 곡 2개씩 수록
    for(int i = 0; i < v.size(); i++) {
        for(int j = 0; j < 2; j++) {
            answer.push_back(v[i].second.second[j].first);
            
            // 장르에 곡이 하나만 있다면 하나만 수록
            if(v[i].second.second.size() == 1) break;
        }
    }
    
    return answer;
}