(C++) - 프로그래머스(고득점 kit - Hash) : 베스트앨범 답

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

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

map과 vector를 이용해 풀었던 문제입니다.

 

 

풀이방법

 1. record맵을 선언해 한 장르에 해당하는 vector {플레이 수,index} 부분을 push해 줍니다. 

 

 2. 각 장르별 곡들의 총합 플레이 수를 구해 map변수 played에 저장합니다.

 

 3. played가 각 장르별을 key로 하여 해당 장르의 총 플레이 수를 구했으므로 이번에는 totalPlayed map변수를 선언하여 played를 순회하며 key를 총 플레이 수로 정하고 value를 장르로 하여 저장합니다. 이러면 totalPlayed변수는 플레이 수가 key로써 오름차순으로 정렬되어 장르를 value로 가지게 됩니다.

 

 4. 속한 노래가 많이 재생된 장르들만 모아서 vector변수 bestPlayedGenre에 저장합니다.

 

 5. bestPlayedGenre에 저장된 장르의 개수만큼 순회하며 한 장르를 key로 하여 record[장르]를 접근한다면 vector {플레이 수,index}를 얻을 수 있습니다. 이후 플레이 수는 내림차순 index는 오름차순이 되도록 정렬해준다음 곡을 answer에 담아줍니다.

Code

#include <bits/stdc++.h>

using namespace std;

bool desc(pair<int, int> a, pair<int, int> b) {
	// 각 원소들을 first에 관해서는 오름차순 정렬을, second에 관해서는 내림차순으로 정렬한다.
	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;
    int size = genres.size();
    map <string, vector<pair<int,int>>> record;
    map <string,int> played;
    map <int,string> totalPlayed;
    vector <string> bestPlayedgenre;
    for(int i = 0; i < size; i++)
        record[genres[i]].push_back({plays[i],i});
    
    for(auto r : record)
        for(auto rs : r.second)
            played[r.first] += rs.first; //각 장르별 총합 플레이 수 구하기
    
    for(auto p : played){
        totalPlayed[p.second] = p.first;
    }

    for(auto t = totalPlayed.rbegin(); t != totalPlayed.rend() ; t++)
        bestPlayedgenre.push_back(t->second); //1. 속한 노래가 많이 재생된 장르를 먼저 push

    for(auto bp : bestPlayedgenre){ 
        vector<pair<int,int>> genresSongList = record[bp];
        
        if(genresSongList.size()==1) { //해당 장르곡이 하나라면 그 곡의 index만 담기
            answer.push_back(genresSongList[0].second); 
            continue;
        } 
        
        sort(genresSongList.begin(),genresSongList.end(),desc); //해당 장르의 {플레이수, index}를 내림차순으로 정렬
        int cnt = 0;
        for(auto oneSong : genresSongList){ //2. 장르 내에서 많이 재생된 노래를 먼저 수록
            if(cnt == 2) break;
            answer.push_back(oneSong.second);
            cnt++;
        }
    }
    
    return answer;
}

int main(){
    vector<string> genres({"classic", "pop"});
    vector<int> plays({50,5000});
    vector <int> answer = solution(genres,plays);
    for(auto a : answer) cout << a << ' ';
}