[프로그래머스 / C++] 베스트앨범

 

문제 링크: programmers.co.kr/learn/courses/30/lessons/42579

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

 

풀이

 

unordered_map에 장르 이름을 key로, (장르별 재생 횟수, (노래의 고유 번호, 노래의 재생 횟수) 배열)을 value로 저장했다. 

 

다음과 같이 문제가 주어졌을 때

genres	plays	return
[classic, pop, classic, classic, pop]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

[classic] : (1450, { (0, 500), (2, 150), (3, 800) } )

[pop] : (3100, { (1, 600), (4, 2500) } )

 

위와 같은 형태로 저장된다.

 

저장된 unordered_map을 vector로 옮긴 다음에 가장 많이 재생된 장르 순서대로 정렬한다. (cmp1)

이후 장르별 노래 중에서 가장 많이 재생된 노래 순서대로 정렬한 뒤(cmp2), 맨 앞의 노래 2곡을 베스트 앨범에 추가한다. 

 

 

 

소스코드

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
bool cmp1(const pair<string, pair<int, vector<pair<int, int>>>>& a, const pair<string, pair<int, vector<pair<int, int>>>>& b) {
    if(a.second.first == b.second.first) return a.first < b.first;
    return a.second.first > b.second.first;
}
 
bool cmp2(const pair<int, int>& a, const pair<int, int>& b) {
    if(a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, pair<int, vector<pair<int, int>>>> m;
 
    for(int i = 0; i < genres.size(); i++) {
        m[genres[i]].first += plays[i]; // 장르별 재생 횟수 증가
        m[genres[i]].second.push_back(make_pair(i, plays[i]));  // 장르별로 노래의 (고유 번호, 재생 횟수) 저장
    }
 
    vector<pair<string, pair<int, vector<pair<int, int>>>>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp1); // 장르별 재생 횟수 내림차순 정렬
 
    for(auto it: v) {
        sort(it.second.second.begin(), it.second.second.end(), cmp2);   // 장르 내 노래별 재생 횟수 내림차순 정렬
        answer.push_back(it.second.second[0].first);
        if(it.second.second.size() > 1) answer.push_back(it.second.second[1].first);
    }
 
    return answer;
}

 

테스트 결과

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)