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

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

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

 

1. 일단 각 노래들을 (장르, 장르 내의 재생 수, 장르 내의 고유번호) 순으로 정렬합니다.

2. 장르 별 재생 수를 map을 이용하여 저장해줍니다.

3. map에 저장된 장르 별 재생 수에 따라 우선순위 큐에 저장해줍니다.

4. 가장 많이 재생된 장르를 우선순위 큐에서 pop해줍니다.

5. 현재 뽑아낸 가장 많이 재생된 장르에 해당하는 노래를 1번 과정에서 정렬한 데이터 속에서 찾아낼 것입니다. 재생 수가 높은, 재생 수가 같다면 고유번호가 낮은 노래를 최대 두 개 골라서 수록해줍니다.

6. 4번으로 돌아가서 과정을 반복합니다.

 

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

bool compare(pair<string, pair<int, int>>& a, pair<string, pair<int, int>>& b) {
    if(a.first == b.first) {
        if(a.second.first == b.second.first) {
            return a.second.second < b.second.second;
        } else {
            return a.second.first > b.second.first;
        }
    } else {
        return a.first < b.first;
    }
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    vector<pair<string, pair<int, int>>> songs;
    map<string, int> nums;
    priority_queue<pair<int, string>> pq;
    for(int i=0; i<plays.size(); i++) {
        songs.push_back({genres[i],{plays[i], i}});
        auto num = nums.find(genres[i]);
        if(num != nums.end()) {
            num->second += plays[i];
        } else {
            nums.insert({genres[i], plays[i]});
        }
    }
    for(auto it = nums.begin(); it != nums.end(); it++) {
        pq.push({it->second, it->first});
    }
    sort(songs.begin(), songs.end(), compare);
    while(!pq.empty()) {
        string genre = pq.top().second;
        pq.pop();
        int cnt = 0;
        for(int i=0; i<songs.size(); i++) {
            if(songs[i].first == genre) {
                answer.push_back(songs[i].second.second);
                cnt++;
                if(cnt == 2) break;
            }
        }
    }
    return answer;
}