[프로그래머스/C++] 알고리즘 고득점 키트 - 베스트앨범

문제와 예시 입출력

 

---

나의 접근 방법

일단 장르별로 어떤 장르가 가장 재생이 많이 됐는지 확인해야 해서

장르별 총 재생 횟수를 담는 해시 맵을 하나 생성했다.

-> 아래 코드에서 hMap에 해당한다.

 

그 다음 단계로 해야하는 것은

1) 가장 인기 있는 장르를 찾아서 

2) 그 장르 내에서 가장 많이 재생된 노래 2곡의 고유 번호를 찾는것이다.

 

그러면 해시맵으로 저장해놓은 자료구조 (hMap)에서 가장 인기 있는 장르를 찾아야하는데,

해시를 정렬할 수는 없으니... 비효율적인 것 같으나 벡터를 하나 더 만들어서 장르 이름과 장르별 총 재생횟수를 담았다. 

-> 아래 코드에서 top_genres에 해당한다.

그렇게 만들어진 벡터 top_genres를 재생횟수에 맞춰 정렬했다. (comp 오버로딩을 했다.)

 

그리고 하나의 벡터를 더 만들었는데,

가장 인기 있는 장르 내에서, 가장 많이 재생된 곡 2개를 뽑아서, 고유 번호를 출력해야했기 때문에,

장르 따로, 재생횟수 따로 있는 데이터들을 하나로 다룰 필요가 있었다.

그래서 genre_play 벡터를 만들었고, 이 벡터는 (장르,(고유번호,재생횟수))를 가지고 있다.

이 genre_play도 재생횟수를 기준으로 내림차순 정렬해준다. (comp2 커스텀)

이렇게 정렬을 한 이유는 아래에서 장르 이름을 가지고 2개의 곡만 찾을 때, 앞에서 2개만 찾으려고 하기 위함이다.

 

그러면 이제 최종적으로 top_genres에 있는 장르 이름을 가지고

genre_play에서 검색하면서 cnt 변수로 최대 2개까지만 찾으며

곡의 고유 번호를 answ 벡터에 넣어 출력한다.

 

---

 

코드 

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

bool comp2(const pair<string, pair<int,int>> &a, const pair<string, pair<int,int>> &b){
    return a.second.second > b.second.second;
    
}
bool comp(const pair<string,int> &a, const pair<string,int> &b){
    return a.second > b.second;
    
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    int temp = 0;
    unordered_map<string,int> hMap;
    vector<pair<string,int>> top_genres;
    vector<pair<string, pair<int,int>>> genre_play;
    vector<int> answer;
    
    for (int i=0;i<genres.size();++i){
        hMap[genres[i]]+=plays[i];
        genre_play.push_back(make_pair(genres[i],make_pair(i,plays[i])));
    }
    
    for (auto a: hMap){
        top_genres.push_back(make_pair(a.first,a.second));
    }
    
    sort(top_genres.begin(),top_genres.end(),comp);
    sort(genre_play.begin(),genre_play.end(),comp2);

    for(int i=0;i<top_genres.size();++i){
        int cnt =0;    
        for (auto a: genre_play){
            if (a.first==top_genres[i].first && cnt<2){
                answer.push_back(a.second.first);
                cnt++;
            }
        }  
    }
    return answer;
}

:: 간단 요약 :: 
- 장르별 총 재생 횟수를 저장하기 위해 unordered_map<string, int> hMap을 만든다.
- 각 노래 정보를 (장르, (고유번호, 재생횟수)) 형태로 저장하는 vector<pair<string, pair<int,int>>> genre_play도 만든다.
- hMap의 내용을 (장르, 총 재생 횟수) 쌍으로 옮겨 top_genres 벡터에 저장한다.top_genres는 총 재생 횟수를 기준으로 내림차순 정렬해서 인기 장르 순으로 정렬한다.
- genre_play는 각 노래의 재생횟수를 기준으로 내림차순 정렬해서, 특정 장르 내에서 인기 노래가 앞에 오도록 정렬한다.
- 정렬된 top_genres 순서대로, genre_play에서 해당 장르 노래를 찾아 최대 2곡씩 결과 벡터 answer에 추가한다. 

위에 너무 횡설수설 작성한 것 같아서 한 번 더 정리해봤다!