[해시] 베스트 앨범

프로그래머스

 

c++ 문법이 익숙하지 않으면 엄청 해맬 수 있는 문제....

 

장르별로 재생 횟수의 합과, 해당 장르의 목록들 각각 정렬하는 문제라 좀 헷갈려서 오래 걸렸다..

장르 별로 재생 횟수의 합으로 정렬된 배열과,

해당 장르의 목록을 정렬한 배열이 필요하다

 

hashmap으로 들어가기 때문에 정렬 시 vector의 도움이 꼭 필요하다는 점..... 명심하자ㅠ

그리고 재생횟수가 같을 경우 더 작은 값을 return해줘야 한다는 것도 꼬옥 기억..~

 

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

using namespace std;

static bool comp(pair<string, int>& a, pair<string, int>& b){
    return a.second > b.second;
}

static bool comp2(pair<int, int>& a, pair<int, int>& 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;
    
    map<string, pair<int, vector<pair<int, int>>>> hashMap;
    
    // int는 계속 더함, vector는 push_back.
    for(int i = 0; i < genres.size(); i++){
        int& sum = hashMap[genres[i]].first; // 현재 sum
        vector<pair<int, int>>& map = hashMap[genres[i]].second; // 현재 vector;
        
        sum += plays[i];
        map.push_back(make_pair(plays[i], i));
    }
    
    // 노래 정렬
    vector<pair<string, int>> sortedGenres;
    
    for(const auto& key : hashMap) sortedGenres.push_back(make_pair(key.first, key.second.first));
    sort(sortedGenres.begin(), sortedGenres.end(), comp); // 내림차순 정렬
    
    for(const auto& key : sortedGenres){
        string name = key.first; // 노래 이름.
        
        int sum = hashMap[name].first;
        vector<pair<int, int>>& map = hashMap[name].second;
        sort(map.begin(), map.end(), comp2);
        
        int cnt = 0;
        
        for(const auto& song : map){
            if(cnt >= 2) break;
            int number = song.second; // 고유 번호
            answer.push_back(number);
            cnt++;
        }
    }
    
    
    return answer;
}​