(프로그래머스 c++)베스트 앨범

map과 multimap을 사용했다.

인덱스와 재생 횟수, 장르, 장르 별 재생 횟수를 다뤄야 하기 때문에 상당히 복잡하게 코딩을 했다.

 

multimap<string, pair<int, int>> mm을 선언하였다.

mm의 key는 genre, value는 재생 횟수와 해당 곡의 인덱스를 pair로 묶어서 값을 넣는다.

 

map<string, int> m.

각 장르별 재생된 총 횟수이다.

 

우선 모든 장르와 재생횟수, 총 재생 횟수를 for문을 통해 모두 다 넣는다.

다음 for문에서는 각 장르별로 2개씩 재생 횟수의 내림차순으로 정렬하여 mm에 넣는 작업을 한다.

내림차순 정렬을 하기 위해 vector<pair<int, int>> v를 선언한다.

해당 장르의 재생 횟수와 인덱스를 v에 넣고 sort한다.

sort의 desc는 pair 형태에 맞게 따로 정의했다.

정렬이 끝나면 원래 있던 mm의 장르를 지우고 for문을 통해 2개씩만 넣는다.

만약 곡이 1개만 있다면 break를 하여 빠져나와야 한다.

 

이제 mm에 2개 이하의 곡이 재생횟수별로 내림차순 정렬되어 들어가있다..!

그럼 while문을 통해 mm이 비어질 때까지 반복하면 된다.

우선 m을 통해 가장 많이 재생된 장르를 선택한다.

장르를 선택했으면 mm에 접근하여 앞에서부터 차례대로 answer에 넣어주고, 해당 value를 지워준다.

만약 곡이 없다면 break.

for문을 빠져나오고 해당 장르의 value가 없으니 m에서도 지워서 다음 장르의 최댓값을 찾을 수 있도록 한다..!

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;

bool desc(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    multimap<string, pair<int, int>> mm;
    map<string, int> m;
    
    for(int i = 0; i < genres.size(); i++)
    {
        mm.insert(make_pair(genres[i], make_pair(plays[i], i)));
        m[genres[i]] += plays[i];
    }
    
    for(auto itr = m.begin(); itr != m.end(); itr++)
    {
        vector<pair<int, int>> v;
        for(auto i = mm.lower_bound(itr->first); i != mm.upper_bound(itr->first); i++)
            v.push_back(i->second);
        sort(v.begin(), v.end(), desc);
        mm.erase(mm.lower_bound(itr->first), mm.upper_bound(itr->first));
        
        for(int i = 0; i < 2; i++)
        {
            if(v.begin() + i == v.end())
                break;
            mm.insert(make_pair(itr->first, v[i]));
        }
    }
    
    while(!mm.empty())
    {
        int max = 0;
        string genre = "";
        
        for(auto itr = m.begin(); itr != m.end(); itr++)
        {
            if(max < itr->second)
            {
                max = itr->second;
                genre = itr->first;
            }
        }
        
        for(int i = 0; i < 2; i++)
        {
            if(mm.lower_bound(genre) == mm.end())
                break;
            answer.push_back(mm.lower_bound(genre)->second.second);
            mm.erase(mm.lower_bound(genre));
        }
        
        if(mm.find(genre) == mm.end())
            m.erase(genre);
    }
    return answer;
}