프로그래머스 - 베스트앨범 - C++

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

프로그래머스

 

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

using namespace std;

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

    unordered_map<string, vector<pair<int, int>>> um;
    unordered_map<string, int> sum;

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

    vector<pair<string, vector<pair<int, int>>>> uv;
    for (auto item : um)
        uv.push_back(item);
    
    sort(uv.begin(), uv.end(),
        [&sum]
        (pair<string, vector<pair<int, int>>>& a, pair<string, vector<pair<int, int>>>& b)
        {
            
            if (sum[a.first] > sum[b.first])return true;
            else return false;
        });

    for (int i = 0; i < uv.size(); i++)
    {
        sort(uv[i].second.begin(), uv[i].second.end(), []
        ( pair<int, int>& a, pair<int, int>& b)
            {
                if (a.second == b.second)
                    return a.first < b.first;
                else if (a.second > b.second)
                    return true;
                else
                    return false;
            });

        answer.push_back(uv[i].second[0].first);
        if(uv[i].second.size()==1)continue;
        answer.push_back(uv[i].second[1].first);
    }

    return answer;
}

주어진 genres와 plays 는 고유번호 i번의 노래장르와 플레이 횟수를 각각 저장하고 있다. 

이를 바탕으로 장르별로 가장많이 재생된 곡을 최대 2곡씩 저장하며, 가장 많이 재생된 장르부터 저장한다. 

 

따라서 장르별로 재생된 횟수의 총합을 저장할 자료구조와 장르별로 노래를 저장해놓을 변수가 각각 필요하다.

굳이 정렬할 필요가 없기에 해시맵으로 구성된 unordered_map을 사용한다. 

 

unordered_map<string, vector<pair<int, int>>> um;

unordered_map<string, int> sum;

um 변수는 각 장르별로 노래를 분류해놓을 변수이다.

sum은 장르별로 재생된 총 횟수를 저장해놓을 변수이다. 

 

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

주어진 데이터를 순회하며 데이터를 분류한다. 

 

그 후, 분류한 데이터를 바탕으로 정렬을 해야한다. 재생된 횟수가 많은 장르를 내림차순으로 정렬해야하기 때문에

vector로 데이터를 옮기고 정렬하는 과정이 필요하다. 

vector<pair<string, vector<pair<int, int>>>> uv;
    for (auto item : um)
        uv.push_back(item);
    
    sort(uv.begin(), uv.end(),
        [&sum]
        (pair<string, vector<pair<int, int>>>& a, pair<string, vector<pair<int, int>>>& b)
        {
            
            if (sum[a.first] > sum[b.first])return true;
            else return false;
        });

sort 에는 람다함수를 사용했다. 

 

장르별로 정렬을 했다면 각 장르에 있는 노래 중 가장 재생이 많이된 노래로 내림차순을 다시 진행해야 한다.

 

for (int i = 0; i < uv.size(); i++)
    {
        sort(uv[i].second.begin(), uv[i].second.end(), []
        ( pair<int, int>& a, pair<int, int>& b)
            {
                if (a.second == b.second)
                    return a.first < b.first;
                else if (a.second > b.second)
                    return true;
                else
                    return false;
            });

        answer.push_back(uv[i].second[0].first);
        if(uv[i].second.size()==1)continue;
        answer.push_back(uv[i].second[1].first);
    }

장르별로 재생이 많이된 순으로 정렬된 uv 벡터를 처음부터 순회하며 각 장르의 노래를 다시 한번 sort함수로 정렬한다.

 

그 후 정렬된 vector의 0,1번 인덱스를 answer에 추가한다. 

조건 중 1개 곡뿐이면 1개만 저장해야하기 때문에 size를 비교하는 구문을 추가했다.