베스트 앨범

programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

#include <string>
#include <vector>
#include<map>
#include<iostream>
#include <algorithm>
using namespace std;


bool cmp(pair<int,int>a, pair<int,int>b){

   return a.first>b.first;
}

bool cmpplays(pair<string,int>a, pair<string,int>b){

   return a.second>b.second;
}


vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string,int>m;
    map<string,vector<pair<int,int>>>idplays;
   
   for(int i=0; i<genres.size(); i++){
        if(m.find(genres[i])==m.end()){
           m[genres[i]] = plays[i]; 
        }
        else{
            m[genres[i]]+=plays[i];
        }
        idplays[genres[i]].push_back(make_pair(plays[i],i)); 
    }
   
    map<string,int>::iterator it;
    vector<pair<string,int>> order;
    for(it=m.begin(); it!=m.end();it++ ){
        order.push_back(make_pair(it->first, it->second));
    }
    sort(order.begin(),order.end(),cmpplays);

    
    map<string,vector<pair<int,int>>>::iterator iter;
    
    for(int i=0; i<order.size(); i++){
        string nowgenre = order[i].first;

        vector<pair<int,int>> list = idplays[nowgenre];
        
        stable_sort(list.begin(),list.end(),cmp);

        if(list.size()==1){answer.push_back(list.front().second);}
        else{
            answer.push_back(list[0].second);
            answer.push_back(list[1].second);
        }


    }
    return answer;
}

- map 자료구조를 이용해서 풀었다

- map 안에 vector<int> 를 정의하면 하나의 인덱스에 대해 리스트 형태로 나열할 수 있다. 리스트 안에는 plays수를 저장했고 오름차순으로 정렬하게 되면 가장 조회수가 높은 두곡을 선택할 수 있게 된다.