[PG] 베스트앨범 [C++]

 

프로그래머스

 

 

문제에서 제시하는 곡을 수록하는 기준, 제한사항을 잘 생각해서 구현하기만 하면 됐다.

 

우선 장르별 총 재생 횟수를 구하기 위한 map(genreCount)과 장르별 각 곡들의 재생 횟수를 담기 위한 map(playCount)을 할당했다.

genreCount의 경우 매개변수로 들어온 벡터를 순회하며 각 장르들의 재생 횟수를 누적해 준다.

이후 벡터로 바꾸어서 정렬해 최종적으로 앨범에 들어갈 장르 순서를 구한다.

 

playCount의 경우 genre를 key로 가지고, {곡 번호, 재생 횟수} pair를 담는 우선순위 큐를 value로 가진다.

저장만 해두면 나중에 genreCount를 정렬하여 먼저 들어갈 장르를 구하고, 그 순서대로 우선순위 큐에서 곡을 2개씩 뽑기만 하면 된다.

우선순위 큐의 정렬 기준은 문제에서 주어진 대로 재생수 내림차순, 재생수가 같다면 곡 번호가 낮은 것이 먼저 오도록 하면 된다.

 

코드

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

#define PII pair<int, int>

using namespace std;

struct cmp {
    bool operator() (PII a, PII b) {
        if (a.second == b.second) {
            return a.first > b.first;
        } else {
            return a.second < b.second;
        }
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> genreCount;
    map<string, priority_queue<PII, vector<PII>, cmp>> playCount;
    for (int i = 0; i < genres.size(); i++) {
        genreCount[genres[i]] += plays[i];
        playCount[genres[i]].push({i, plays[i]});
    }
    
    vector<pair<string, int>> genreCountVector(genreCount.begin(), genreCount.end());
    
    sort(genreCountVector.begin(), genreCountVector.end(), [&](pair<string, int> a, pair<string, int> b) {
       return a.second > b.second; 
    });
    
    for (int i = 0; i < genreCountVector.size(); i++) {
        int songs = 0;
        while (!playCount[genreCountVector[i].first].empty() && songs != 2) {
            answer.push_back(playCount[genreCountVector[i].first].top().first);
            playCount[genreCountVector[i].first].pop();
            songs++;
        }
    }
    
    return answer;
}