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

• 출처: 프로그래머스 42579
• 분류: 해시 · Lv.3

문제

장르 배열 genres와 재생수 배열 plays가 주어진다. 장르별로 재생수 합이 큰 순서대로, 각 장르에서 재생수 상위 2곡의 인덱스를 반환하라. 재생수가 같으면 인덱스가 낮은 곡 우선. 장르에 곡이 하나면 하나만 수록.

핵심

해시맵 2개로 정리한다. 하나는 장르별 총 재생수, 하나는 장르별 곡 목록. 총 재생수로 장르 순서를 정하고, 각 장르 내에서 재생수 내림차순 정렬 후 최대 2곡을 뽑는다.

풀이

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    unordered_map<string, int> total;
    unordered_map<string, vector<pair<int, int>>> songs; // {plays, index}

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

    // 장르를 총 재생수 내림차순으로 정렬
    vector<string> order;
    for (const auto& [genre, _] : total)
        order.push_back(genre);
    sort(order.begin(), order.end(), [&](const string& a, const string& b) {
        return total[a] > total[b];
    });

    vector<int> answer;
    for (const auto& genre : order) {
        auto& v = songs[genre];
        // 재생수 내림차순, 같으면 인덱스 오름차순
        sort(v.begin(), v.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
            return a.first != b.first ? a.first > b.first : a.second < b.second;
        });
        for (int i = 0; i < min((int)v.size(), 2); i++)
            answer.push_back(v[i].second);
    }

    return answer;
}

메모

• 해시맵이 2개 필요한 이유: total은 장르 간 순서를 정하는 용도, songs는 장르 내 곡을 정렬하는 용도. 역할이 다르다.
• pair<int, int>에서 plays를 first로 둔 이유: sort 비교 시 first부터 비교하므로 재생수 기준 정렬이 자연스럽다.
• min((int)v.size(), 2): v.size()는 size_t(unsigned)라서 int와 비교하려면 캐스팅이 필요하다.
• 장르 순서를 정할 때 order 벡터를 따로 만드는 이유: unordered_map은 순회 순서가 보장되지 않으므로, 키를 꺼내서 별도로 정렬해야 한다.

복잡도

시간	공간
O(N log N)	O(N)

N = 곡 수. 장르 내 정렬이 지배적이고, 모든 장르의 곡 수 합이 N이므로 전체 O(N log N).