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

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

문제 링크

위장과 마찬가지로 C++의 map을 활용해서 풀 수 있는 문제였다. 장르별로 노래를 보관하는 배열을 가지고 있고, 노래가 추가될 때마다 재생 횟수와 고유 번호에 따라 정렬해 주도록 한다. 이 작업이 완료되면 속한 노래가 많이 재생된 장르 순서대로 앨범에 노래를 넣어 주어야 하는데, 이를 위해서 속한 노래의 모든 재생 횟수를 키로 가지고 장르 이름을 값으로 가지는 맵을 하나 더 선언해 주었다. 맵은 키에 따라 자동으로 오름차순으로 정렬되는데, 내림차순이 필요하기 때문에 -1을 곱해 주었다. 맵을 사용할 수 있었던 건 모든 장르는 재생된 횟수가 다르다는 조건 때문이었다. 자동으로 장르별로 내림차순 정렬이 되었으므로, 이제 이 순서를 따라 장르별로 노래를 넣어 준다. 장르에 속한 곡이 하나인지 확인하고, 만약 하나라면 하나의 곡만 선택하도록 한다.

풀이

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
using pii = pair<int, int>; // 재생 횟수, 고유 번호

bool comp(pii a, pii b){
    if(a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    map<string, vector<pii>> m;

    for(int i = 0; i < genres.size(); i++){
        vector<pii> tmp;
        tmp = m[genres[i]];
        tmp.push_back(pii(plays[i], i));
        sort(tmp.begin(), tmp.end(), comp);
        m[genres[i]] = tmp;
    }

    map<int, string> order;

    for(auto p : m){
        int sum = 0;
        for(auto v : p.second) {
            sum += v.first;
        }
        sum *= -1;
        order[sum] = p.first;
    }

    for(auto p : order) {
        if(m[p.second].size() == 1){
            answer.push_back(m[p.second][0].second);
        }
        else {
            answer.push_back(m[p.second][0].second);
            answer.push_back(m[p.second][1].second);
        }
    }

    return answer;
}