프로그래머스/lv3/42579. 베스트앨범

#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

struct Song {
    int num;
    int plays;
    Song(int num, int plays) : num(num), plays(plays) {}

    bool operator<(const Song& s) const { return plays > s.plays; }
};

int oper(pair<string, pair<int, multiset<Song>>> s1,
         pair<string, pair<int, multiset<Song>>> s2) {
    return s1.second.first > s2.second.first;
}

vector<int> solution(vector<string> g, vector<int> p) {
    vector<int> ans;

    map<string, pair<int, multiset<Song>>> m;

    for (int i = 0; i < p.size(); i++) {
        m[g[i]].first += p[i];
        m[g[i]].second.insert(Song(i, p[i]));
    }

    vector<pair<string, pair<int, multiset<Song>>>> v;

    for (auto i : m)
        v.push_back({i.first, {i.second.first, i.second.second}});

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

    for (auto i : v) {
        auto k = m[i.first].second;
        int cnt = 0;
        for (auto l : k) {
            ans.push_back(l.num);
            cnt++;
            if (cnt > 1) break;
        }
    }
    return ans;
}

조건이 많은 문제였다. 장르명 / 그 장르의 총 재생횟수 / 노래의 고유 번호, 노래의 재생된 횟수까지 4개가 있었다.
노래 정보는 구조체로 묶고, 사용자 정의 데이터 형태이므로 연산자 오버로딩을 통해 multiset 안에서 재생 횟수가 많은 순으로 자동 정렬되게 만들었다.
장르 별 총 재생 횟수는 pair로 만든 value값에 first로 접근하여 더해준다.
장르에 삽입 될 노래들은 Song 구조체를 생성한 뒤 multiset에 고유번호, 노래의 재생된 횟수 형식으로 넣는다.

이렇게 하게 된다면 장르 안의 노래들은 재생 횟수가 많은 순으로 정렬이 될 것이다.
다만 내가 따로 해야 할 일은 모든 장르의 장르 별 총 재생 횟수가 내림차순으로 정렬하는 것이다.
vector에 따로 할당해서 s1.second.first(총 재생 횟수) 별로 정렬되게 operator를 만들고 정렬했다.
그 뒤 루프 돌면서 속한 노래가 많이 재생된 장르 순으로 하나씩 꺼내고 inner loop에서 노래들의 자동 정렬된 고유번호를 answer에 할당했다.