베스트 앨범

• map을 적절하게 사용한 풀이가 핵심이다
• map에서 특정 value로 sort하려면 vector에 복사 후 compare함수를 작성해야 했다! (매우중요 -_-)
• map은 pair를 사용한 구조로 되어있음을 망각하면 안된다
• map / vector와 같은 container의 사용에 익숙해져야 함을 또 다시 깨달았다...

코드

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

using namespace std;
bool compare (pair<string, int> a, pair<string, int> b){
    if(a.second > b.second) return true;
    return false;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> m;
    map<string, vector<pair<int,int>>> v;
    for(int i=0;i<genres.size();i++)
    {
        // 장르별 개수 구하기
        m[genres[i]] += plays[i];
        // 장르별 2쌍의 인덱스/개수 저장
        if(v[genres[i]].size() == 0)
            v[genres[i]].push_back({i,plays[i]});
        else if(v[genres[i]].size() == 1){
            if(v[genres[i]][0].second > plays[i])
                v[genres[i]].push_back({i,plays[i]});
            else
                v[genres[i]].insert(v[genres[i]].begin(),{i,plays[i]});
        }else{
            if(v[genres[i]][0].second < plays[i]){
                v[genres[i]].insert(v[genres[i]].begin(),{i,plays[i]});
                v[genres[i]].erase(v[genres[i]].end()-1);
            }else if(v[genres[i]][1].second < plays[i])
                v[genres[i]][1] = {i,plays[i]};
        }
    }
    /* map에서 특정 value로 sort하려면 vector에 복사해야 한다! */
    vector<pair<string,int>> tmp(m.begin(), m.end());
    sort(tmp.begin(), tmp.end(), compare);

    /* 정렬된 순서대로 값을 삽입! */
    for(auto it=tmp.begin();it != tmp.end();it++)
    {
        for(int j=0;j < v[it->first].size();j++)
        {
            answer.push_back(v[it->first][j].first);
        }
    }
    return answer;
}