[프로그래머스/C++] 베스트앨범

1.문제 링크

베스트앨범

2. 풀이 전 계획과 생각

• map 자료구조 사용

3. 풀이

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

bool cmp1(const pair<string,int>& a, const pair<string,int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

bool cmp2(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;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    map<string, int> m;
    for(int i=0;i<genres.size();i++){
        if(m.find(genres[i])!=m.end()){
            // find
            m[genres[i]]+=plays[i];
        }
        else{
            // not find
            m[genres[i]] = plays[i]; 
            //m.insert({geners[i], plays[i]});
        }
    }
    
    vector<pair<string,int>> v( m.begin(), m.end() );
    sort(v.begin(), v.end(), cmp1);
    
    vector<int> answer;
    for(int i=0;i<v.size();i++){
        vector<pair<int,int>> temp;
        for(int j=0;j<plays.size();j++){
            if(genres[j]==v[i].first){
                temp.push_back({plays[j], j}); // time index
            }
        }
        sort(temp.begin(), temp.end(), cmp2);
        answer.push_back(temp[0].second);
        if(temp.size()>1) answer.push_back(temp[1].second);
    }

    return answer;
}

map 자료구조에 key 값을 장르, value를 재생 횟수 누적합을 저장한다.

map 자료구조를 value 값을 기준으로 내림차순하기 위해 vector에 데이터를 옮긴다.

내림차순한 vector 자료구조를 순회하면서 각 재생시간과 index를 temp vector에 저장하고 temp vector를 재생시간을 기준으로 내림차순해 최대 2개까지의 고유 번호를 각각 저장한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• map 자료구조에서 value를 기준으로 정렬하는 법을 알게됨. map 자료구조는 기본적으로 key를 기준으로 오름차순 정렬이 되어있다. value를 기준으로 정렬하고 싶을 때 vector에 데이터를 옮겨 정렬한다.