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

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

문제

 

---

풀이

 

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

장르별 노래 재생횟수 map에 {key = 장르명, value = 재생 횟수 합} 형태로 저장한다.

이후 정렬을 할 때는 vector에 옮겨서 수행한다. 

cmp2, 정의 함수를 사용해서 내림차순으로 정렬한다.

// 장르별 재생횟수 합 내림차순으로 정렬
vector<pair<string, int>> temp(m2.begin(), m2.end()); 
sort(temp.begin(), temp.end(), cmp2);

...

 bool cmp2(pair<string, int> &a, pair<string, int> &b){
    return a.second > b.second; // 재생 횟수 합 내림차순
}

 

 

2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 

map을 사용해서 장르별로 노래를 구분해서 저장한다. {key = 장르명, value = 노래 저장할 vector}

노래 고유 번호를 이용한 정렬이 필요하기 때문에, pair {고유번호, 재생횟수} 형태로 저장해야한다.

 

이후 장르 노래를 담은 벡터를 정렬할 때는 cmp1, 정의 함수를 사용한다.

기본은 재생 횟수 내림차순으로, 재생 횟수가 같을 때는 고유 번호 오름차순으로 정렬한다. 

bool cmp1(pair<int, int> &a, pair<int, int> &b){
    if(a.second == b.second){
        return a.first < b.first; // 고유 번호 오름차순
    }
    return a.second > b.second; // 재생 횟수 내림차순
}

 

 

전체 풀이

장르의 곡이 하나라면 하나만 선택해야하는 제한사항을 주의해야한다.

#include <bits/stdc++.h>
using namespace std;

bool cmp1(pair<int, int> &a, pair<int, int> &b){
    if(a.second == b.second){
        return a.first < b.first; // 고유 번호 오름차순
    }
    return a.second > b.second; // 재생 횟수 내림차순
}

bool cmp2(pair<string, int> &a, pair<string, int> &b){
    return a.second > b.second; // 재생 횟수 합 내림차순
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> ans;
    map<string, vector<pair<int, int>>> m1; // 장르별 (고유번호, 재생횟수) 저장
    map<string, int> m2; // 장르별 재생횟수 합 저장
    
    // 장르별 음악 저장, 재생횟수 합 저장
    for(int i=0; i<genres.size(); i++){
        string genre = genres[i];
        int play = plays[i];
        if(m1.find(genre)!= m1.end()){
            m1[genre].push_back({i, play});
            m2[genre]+= play;
        }
        else{
            m1.insert({genre, {{i, play}}});
            m2.insert({genre, play});
        }
    }
    
    // 장르별 재생횟수 합 내림차순으로 정렬
    vector<pair<string, int>> temp(m2.begin(), m2.end()); 
    sort(temp.begin(), temp.end(), cmp2);
    
    for(auto t: temp){
        string genre = t.first;
        vector<pair<int, int>> songs = m1[genre];
        // 장르 내 정렬 
        sort(songs.begin(), songs.end(), cmp1);
        
        // 2번째 곡까지 추가
        for(int i=0; i<songs.size() && i<2; i++){
            ans.push_back(songs[i].first);
        }
    }
    
    return ans;
}