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

프로그래머스 베스트앪범 C++ 풀이

 

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

 

// map 만들어서 장르(string)과 재생횟수, 인덱스 담는다.
// 구조체 만들어서 장르별 재생횟수 큰 순서대로 정렬
// map에서 장르안에서 재생횟수 큰 순서대로 정렬
// 장르별 재생횟수 마다 그 장르 안에서 재생횟수 큰 순서대로 2개 이중 for문 돌려서 answer에 push

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

struct tsum{
    int sum;
    string name;
};

//장르 정렬
bool comp(tsum a, tsum b){
    return a.sum > b.sum;
}

//곡 정렬
bool idxcomp(pair<int, int> a, 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) {
    vector<int> answer; //정답
    map<string, vector<pair<int, int>>> mp; // 장르와 곡리스트(인덱스와 함께)들
    vector<tsum> t_sum; //장르의 총 재생수와 인덱스, 장르명
    
    //자료구조
    //{"classic":[500, 150, 800], "pop":[600, 2500]}
    for(int i = 0; i < genres.size(); i++){
        mp[genres[i]].push_back({plays[i], i});
    }
    
    // 장르 합이 제일 큰것을 찾기
    for(auto m = mp.begin(); m != mp.end(); m++){
        int sum = 0;
        for(int j = 0; j < genres.size(); j++){
            if(m->first == genres[j]){
                sum += plays[j];
            }
        }
        t_sum.push_back({sum, m->first});
    }
    // 장르 합이 큰것부터 정렬한다.
    sort(t_sum.begin(), t_sum.end(), comp);
    
    // 정렬된 키 순으로 2개씩 구하기
    for(auto m = mp.begin(); m != mp.end(); m++){
        // 정렬을 하되 인덱스도 고려하면서 정렬
        sort(m->second.begin(), m->second.end(), idxcomp);
    }
    
    //재생수가 많은 장르부터 반복문 시작
    for(int i = 0; i < t_sum.size(); i++){
        // 아래 반복 조건은 장르의 갯수 만큼이면서 2개 미만인 경우다 즉 1개 혹은 2개만 추출한다.
        for(int j = 0; j < mp[t_sum[i].name].size() && j < 2; j++){
            //곡이 정렬되어 있는 장르에서 상위 2개의 곡의 인덱스를 꺼낸다.
            answer.push_back(mp[t_sum[i].name][j].second);
        }
    }
    return answer;
}