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

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

문제 링크

#include "header.h"
using namespace std;
map <string, vector<pair<int, int>>> songs;
map <string, int> total;

int desc(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}
int cmp(pair<string, int>a, pair<string, int>b){
    return a.second > b.second;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    for(int i=0; i<genres.size(); i++){
        vector <pair<int, int>> temp = songs[genres[i]];
        temp.push_back({plays[i], i});
        songs[genres[i]] = temp;
        total[genres[i]] += plays[i];
    }

    vector<pair<string, int>> v;

    map<string,int>::iterator iter;
    for(iter= total.begin(); iter != total.end(); iter++){
        v.emplace_back(make_pair(iter->first, iter->second));
    }

    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<v.size(); i++){
        vector <pair<int, int>> temp_v = songs[v[i].first];
        sort(temp_v.begin(), temp_v.end(), desc);
        answer.push_back(temp_v[0].second);
        if(temp_v.size() <= 1) continue;
        answer.push_back(temp_v[1].second);
    }

    return answer;
}

• 단순 해시 구현 문제.
• total 맵은 (장르 이름, 총 재생 수) 이다.
• songs 맵은 (장르 이름, (곡 재생 수, 곡 고유 번호)) 이다.
• total 맵을 벡터로 바꿔준 후 sort 해줘서 많이 재생된 장르 순으로 정렬한다.
• 이제 벡터의 사이즈만큼 돌면서 (장르 갯수) songs의 해당 곡들을 sort 해 준다.
• 첫번째 곡을 넣고, 두번째 곡이 있으면 두번째 곡도 넣는다.