JArchive 프로그래밍 일기

문제

베스트앨범 프로그래머스 level3

리뷰

해시 카테고리의 문제다.

map을 잘 다루면 풀 수 있는 문제였다.

장르 별로 가장 많이 재생된 노래 2개 씩 모아 앨범을 출시한다.

1. 속한 노래가 많이 재생된 장르를 내림차순으로 정렬한다.

// 장르명, 재생횟수 
map<string, int> genre_cnt;

2. 장르 내에서 많이 재생된 노래를 내림차순으로 정렬한다.

// 장르명 string,   <재생횟수, 고유번호> pair로 vector를 저장한다. 
map<string, vector<pair<int,int>>> genre_playlist;  

3. 장르 내에서, 재생횟수가 같은 노래 중에는 고유번호가 낮은 노래를 수록한다.

// 장르명, 재생횟수를 저장한다. 
vector<pair<string, int>> genre_v;

코드

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

bool compare(pair<int,int> a, pair<int,int> b){
    return a.first > b.first; // 재생횟수 내림차순  
}

bool compare_song_cnt(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> genre_cnt; // 장르별 재생횟수 
    map<string, vector<pair<int,int>> > genre_playlist; // 장르별 노래의 재생횟수 및 고유번호
    vector<pair<string, int>> genre_v;  // 장르별 노래 개수 

    for(int i = 0; i < genres.size(); i++){
        genre_cnt[genres[i]] += plays[i]; // 장르별 재생횟수 누적
        genre_playlist[genres[i]].push_back({plays[i], i}); // 장르별 노래의 재생횟수 및 고유번호 
    } 

     // 재생횟수를 이용하여 내림차순 정렬 
    for( auto &song : genre_playlist){
        sort(song.second.begin(), song.second.end(), compare);    
    }    

     genre_v.assign(genre_cnt.begin(), genre_cnt.end()); // 장르별 노래 개수
    sort(genre_v.begin(), genre_v.end(), compare_song_cnt); // 내림차순  

    for(int i = 0; i <genre_v.size(); i++){ // 장르 종류만큼 반복

        string genre_name = genre_v[i].first; // 장르 이름  

        // genre_playlist 에서 최대 2곡까지 선택 가능 (j < 2)
        for(int j = 0; ( j <genre_playlist[genre_name].size() && j < 2 ); j++){ 
            answer.push_back(genre_playlist[genre_name][j].second);
        } 
    }

    return answer;
}