베스트앨범 (프로그래머스)

 

우선 구조체 INFO를 선언한다. INFO 구조체에는 고유번호와 재생 횟수 값이 저장된다. 이제 해시 컨테이너를 통해 해당 장르의 INFO들을 기록한다. (key값 : 장르, value값 : INFO들을 담은 vector 컨테이너) 이때 2번 기준인 "장르 내에서 많이 재생된 노래를 먼저 수록합니다."를 만족시키기 위해 value값을 재생 횟수 기준으로 내림차순 정렬을 해준다. 그리고 3번 기준 "장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다." 만족 시키기 위해 정렬시 재생 횟수가 같은 경우 고유번호 기준으로 오름차순 정렬을 한다. 

 

이제 1번 기준인 "속한 노래가 많이 재생된 장르를 수록합니다."를 만족하기 위해 총 재생 횟수 기준으로 정렬을 진행해야 한다. 이 작업을 위해 map 컨테이너를 사용한다. map 컨테이너는 삽입시 자동으로 정렬을 한다. 

 

기본 오름차순 정렬이므로, 이제 map 컨테이너의 맨 뒤 원소부터 맨 첫번째까지 순회를 돌며 재생 횟수가 가장 많은 장르 이름을 가져온다. 그리고 그 장르 이름에 대한 INFO vector 컨테이너를 해시 컨테이너에서 가져온다. 베스트엘범을 두 개씩 모아 출시하므로 INFO vector 컨테이너를 처음부터 최초 두번 뽑는다. (만약 하나만 있다면 한개만 뽑게된다.) 

 

코드는 다음과 같다.

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

struct INFO
{
    int id;
    int play_count;
};

bool cmp(INFO a, INFO b)
{
    return a.play_count > b.play_count;
}

vector<int> solution(vector<string> genres, vector<int> plays) 
{
    vector<int> answer;
    unordered_map<string, vector<INFO>> d;
    map<int, string> md;
    for(int i = 0; i < genres.size(); ++i) d[genres[i]].push_back(INFO{i, plays[i]});
    for(auto& iter : d)
    {
        sort(iter.second.begin(), iter.second.end(), cmp);
        int count = 0;
        for(const auto info : iter.second) count += info.play_count;
        md[count] = iter.first;
    }
    for(auto iter = md.rbegin(); iter != md.rend(); ++iter)
    {
        int count = 0;
        for(const auto info : d[(*iter).second])
        {
            if(count == 2) break;
             answer.push_back(info.id);
            ++count;
        }      
    }
    return answer;
}