(c++)프로그래머스 코딩테스트 연습-베스트앨범

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

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

[풀이]

구현한 것

1. 먼저 고유번호를 vector<int>Music에 저장하여 장르가 같은 것끼리 붙도록 정렬

2. 각 장르에 속한 노래들을 재생한 횟수 vector<pair<string,int>>num_of_G에 저장

3. 각 장르에 속한 노래 고유번호 map<string, vector<int>>Total에 저장(index는 장르)

4. 재생 횟수가 많은 순으로 num_of_G정렬

5. 재생 횟수 많은 장르 순서대로 각각 속한 노래들을 재생 횟수 많은 순으로 Total정렬 -> 가장 앞의 두 곡씩 answer에 저장

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

using namespace std;

vector<string>Genres;
vector<int>Plays;
vector<int>Music;//고유번호
vector<pair<string,int>>num_of_G;//각 장르별 재생된 수
map<string,vector<int>>Total;//각 장르에 속하는 노래의 고유번호

//장르 같은 것끼리 붙여놓기
bool sortMusic(int &A, int &B){
    return Genres[A]<Genres[B];
}

//재생 많이 된 장르순으로 정렬
bool sortGenres(pair<string,int> &A, pair<string,int> &B){
    return A.second>B.second;
}

//장르 내에서 많이 재생된 노래순으로 정렬
bool sortTotal(int &A,int &B){
    if(Plays[A]==Plays[B])
        return A<B;
    return Plays[A]>Plays[B];
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    Genres=genres;
    Plays=plays;
    for(int i=0;i<Plays.size();i++)
        Music.push_back(i);
    //장르 같은 것끼리 고유번호 묶기
    sort(Music.begin(),Music.end(),sortMusic);
    //각 장르에 속한 노래들의 재생 횟수 합 저장
    //각 장르에 속한 노래들 저장
    int musics=plays[Music[0]];
    Total[genres[Music[0]]].push_back(Music[0]);
    for(int i=1;i<Music.size();i++){
        if(genres[Music[i]]!=genres[Music[i-1]]){
            num_of_G.push_back(make_pair(genres[Music[i-1]],musics));
            musics=plays[Music[i]];
        }
        else{
            musics+=plays[Music[i]];
        }
        Total[genres[Music[i]]].push_back(Music[i]);
    }
    num_of_G.push_back(make_pair(genres[Music[Music.size()-1]],musics));
    //재생 횟수 많은 순으로 장르 정렬
    sort(num_of_G.begin(),num_of_G.end(),sortGenres);
    //각 장르에 대해 많이 재생된 노래순으로 정렬 후 2개씩 저장
    for(int i=0;i<num_of_G.size();i++){
        string genre=num_of_G[i].first;
        sort(Total[genre].begin(),Total[genre].end(),sortTotal);
        if(Total[genre].size()==1)
            answer.push_back(Total[genre][0]);
        else{
            answer.push_back(Total[genre][0]);
            answer.push_back(Total[genre][1]);
        }
        
    }
    return answer;
}