[프로그래머스] 해시 - 베스트앨범

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

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래 두 개씩 모아 베스트 앨범 출시하기

제한사항

속한 노래가 많이 재생된 장르부터 수록한다.
장르 내에서 많이 재생된 순서로 노래를 수록한다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래부터 수록한다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하이다.
고유번호는 index이다.
장르 종류는 100개 미만이다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택한다.
모든 장르는 재생된 횟수가 다르다.

문제풀이

장르 별 총 재생 횟수가 많은 것부터 적은 순서로 정렬해서 이 순서로 노래를 수록한다.
같은 장르 속 노래들을 재생 횟수가 많은 것부터 적은 순서로 정렬해서 이 순서로 노래를 수록한다.
재생 횟수가 같다면 인덱스가 작은 것부터 큰 순서로 정렬한다.
만약 장르 속 노래가 하나라면 하나만 선택한다.
두개 이상이면 가장 재생이 많이 된 노래 2개를 선택한다.

코드

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

using namespace std;

bool cmp_genres(const pair<string,int>& a, const pair<string,int>& b) {
	return a.second > b.second;
}

bool cmp_plays(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, vector<pair<int, int>>> gp_map;
    unordered_map<string, int> gp_sum;

    for(int i=0; i<genres.size(); i++){
        gp_sum[genres[i]] +=plays[i];
        gp_map[genres[i]].push_back(pair(i, plays[i]));
    }
    
    vector<pair<string,int>> gp_sumV(gp_sum.begin(), gp_sum.end());
    sort(gp_sumV.begin(), gp_sumV.end(), cmp_genres);
    
    for(int i=0; i<gp_sumV.size(); i++){
        string genre = gp_sumV[i].first;
        
        if(gp_map[genre].size() == 1){
            answer.push_back(gp_map[genre][0].first);
        }
        else{
            sort(gp_map[genre].begin(), gp_map[genre].end(), cmp_plays);
            answer.push_back(gp_map[genre][0].first);
            answer.push_back(gp_map[genre][1].first);
        }
    }
    
    return answer;
}

시간 복잡도

O(N*MlogM)
N : 장르 개수
M : 장르 속 노래 최대 개수

문제 풀 때 참고 사이트

C++ Map을 value 기준으로 정렬하기