베스트앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

문제 요약:

스트리밍 사이트에서 장르별로 가장 많이 재생된 노래를 두 곡씩 모아 베스트 앨범을 만들려고 합니다. 노래의 장르와 재생 횟수가 주어질 때, 아래 조건을 만족하는 노래들의 고유 번호를 반환해야 합니다.

1. 장르의 총 재생 횟수가 많은 순서대로 수록합니다.
2. 같은 장르 내에서는 재생 횟수가 많은 노래를 먼저 수록합니다.
3. 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

해결 방법 요약:

1. 장르별 재생 횟수 합계 계산:
   • 각 장르별로 모든 노래의 재생 횟수를 합산하여, 어떤 장르가 가장 많이 재생되었는지 파악합니다.
2. 장르 내 노래 정렬:
   • 각 장르 내에서 노래를 재생 횟수에 따라 내림차순으로 정렬합니다. 재생 횟수가 같다면 고유 번호가 낮은 순서로 정렬합니다.
3. 장르별로 상위 2곡 선택:
   • 각 장르에서 가장 많이 재생된 상위 2곡의 고유 번호를 선택합니다. 만약 곡이 하나만 있는 경우에는 그 곡만 선택합니다.
4. 장르 순서대로 앨범에 곡 추가:
   • 장르별 재생 횟수 합계가 높은 장르부터 순서대로, 상위 2곡의 고유 번호를 앨범에 추가합니다.

 

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) 
{
    vector<int> answer;

    // 장르별 재생 횟수 및 노래 정보 기록
    unordered_map<string, unordered_map<int, int>> PlayList;
    unordered_map<string, int> genre_play_count;

    for (int i = 0; i < genres.size(); i++)
    {
        PlayList[genres[i]][i] = plays[i];
        genre_play_count[genres[i]] += plays[i];
    } 

    // 장르별 총 재생 수를 내림차순으로 정렬
    map<int, string> Record;

    for (const auto& genre : genre_play_count)
    {
        Record[-genre.second] = genre.first; // 재생 횟수 내림차순으로 정렬
    }

    // 각 장르별로 곡을 내림차순 정렬하여 상위 2곡을 선택
    for (const auto& element : Record)
    {
        const string& genre = element.second;
        vector<pair<int, int>> songs;

        for (const auto& song : PlayList[genre])
        {
            songs.push_back({song.second, song.first}); // (재생수, 번호)
        }

        // 재생수 내림차순, 재생수가 같으면 고유 번호 오름차순 정렬
        sort(songs.begin(), songs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first == b.first)
                return a.second < b.second;
            return a.first > b.first;
        });

        // 상위 2곡 추가
        answer.push_back(songs[0].second);
        if (songs.size() > 1)
            answer.push_back(songs[1].second);
    }

    return answer;
}