[프로그래머스] Lv.3 베스트앨범 c++

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

프로그래머스

 

스트리밍 사이트에서 장르별로 가장 많이 재생된 노래를 모아 베스트 앨범을 출시하려고 합니다. 각 노래는 고유 번호로 구분되며, 베스트 앨범에 수록할 노래를 선택하는 기준은 다음과 같습니다:

1. 장르별 총 재생 횟수가 많은 장르부터 수록합니다.
2. 각 장르 내에서 재생 횟수가 많은 노래를 먼저 수록합니다.
3. 재생 횟수가 같은 경우, 고유 번호가 낮은 노래를 먼저 수록합니다.

이 문제는 genres와 plays라는 두 개의 배열을 기반으로, 주어진 조건에 맞게 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 반환하는 함수를 구현해주세요.

 

풀이 방법

문제를 처음 접했을 때 정렬이 핵심이라는 것을 알았지만, 어떻게 정렬해야 할지 고민을 많이 했습니다.

장르별 총 재생 횟수를 기준으로 가장 많이 듣는 장르 순서를 정한 뒤, 각 장르 내에서 가장 많이 플레이된 노래를 우선적으로 정렬해야 했기 때문에, 두 개의 custom sort 함수를 만들었습니다.

• cmp_genre : 장르별 총 재생 횟수를 기준으로 내림차순 정렬.
• cmp_genre_index : 장르 내 곡들의 재생 횟수를 기준으로 내림차순, 재생 횟수가 같을 경우 고유 번호 오름차순으로 정렬.

또한, 두 개의 unordered_map 자료구조와 하나의 정렬을 위한 vector 자료구조를 선언했습니다.

• unordered_map<string, int>: 각 장르의 총 재생 횟수를 저장.
• unordered_map<string, vector<pair<int, int>>>: 각 장르 내의 곡 정보(재생 횟수와 고유 번호)를 저장.
• vector<pair<string, int>>: 장르별 총 재생 횟수를 정렬하기 위해 사용.

정렬에 익숙하시다면 풀어볼만한 문제라고 생각합니다.

 

풀이 코드

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

unordered_map<string,int> total_listening;
unordered_map<string, vector<pair<int, int>>> genre_index;

bool cmp_genre(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second > b.second;
}
bool cmp_genre_index(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) {
    vector<int> answer;
    for(int i=0; i<genres.size(); i++){
         total_listening[genres[i]] += plays[i];
         genre_index[genres[i]].push_back({plays[i],i});
    }
    
    vector<pair<string,int>> sorted_genre;
    for(auto& iter : total_listening){
        sorted_genre.push_back({iter.first, iter.second});
    }
    sort(sorted_genre.begin(), sorted_genre.end(), cmp_genre);
    
    for(auto& iter : genre_index){
        sort(iter.second.begin(), iter.second.end(), cmp_genre_index);
    }
    
    for(int i=0; i<sorted_genre.size(); i++){
        string curr_genre = sorted_genre[i].first;
        if(genre_index[curr_genre].size() == 1){
            answer.push_back(genre_index[curr_genre][0].second);
        }
        else{
            answer.push_back(genre_index[curr_genre][0].second);
            answer.push_back(genre_index[curr_genre][1].second);
        }
    }
    return answer;
}