[c++] 프로그래머스 42579 :: "베스트 앨범" 풀이 및 코드

문제

베스트 앨범 문제 바로가기

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

 

풀이

우선 알아내야 할 것은 다음과 같다.

• 장르의 총 재생 횟수 -> 장르 순위 정하기
• 각 장르의 개별 곡 재생 횟수 -> 곡 순위 정하기

이걸 한 번에 알아내려고 하면 장르를 key로 두고 있는 map에 value로 (총 재생 횟수, index마다의 재생횟수)을 저장해두어야 하고 이러면 장르의 순위를 알아내기 힘들 뿐만 아니라 곡 순위도 추출해서 나타내야 한다. 따라서 map을 두개로 나누었다.

1번 map은 { key : 장르, value : 총 재생 횟수 } 를 나타내고,

2번 map은 { key : 장르, value : { key : 장르/index , value : 재생 횟수 }} 를 나타낸다.

 

위와 같이 map으로 다 저장한 후 1번 map을 정렬해서 장르의 순위를 정하고,

순위 별로 2번 map에서 value 값인 map을 꺼내서 정렬하면 1, 2 순위 곡의 index를 알 수 있다.

 

그런데 map을 어떻게 value 값 기준으로 정렬할까? map은 기존에 key 값을 기준으로 정렬하도록 되어있다.

아래와 같이 vector로 만들어 준 후에 sort 함수를 사용해주면 된다.

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

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

map<string, int> sortMap;
vector<pair<string,int>> sortVec(sortMap.begin(), sortMap.end());
sort(sortVec.begin(), sortVec.end(), compare);

 

 

코드

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

using namespace std;

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

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    map<string, int> genreMap; // 장르 -> 총 재생횟수
    map<string, map<string, int>> genreIndexMap; // 장르 -> 장르+index -> 재생횟수
    
    for(int i=0; i<genres.size(); i++){
        string genre = genres[i];
        int play = plays[i];
        if (genreMap[genre]) {
            genreMap[genre] += play;
        } else {
            genreMap[genre] = play;
        }
        genreIndexMap[genre][genre.append("/"+to_string(i))] = play; // "/"로 split 할 수 있게 하기
    }
    
    // map을 vector로 바꾸어 value 기준 정렬
    vector<pair<string,int>> genreVec(genreMap.begin(), genreMap.end());
    sort(genreVec.begin(), genreVec.end(), compare);
    
    for(auto iter = genreVec.begin(); iter != genreVec.end(); iter++) {
        string nowGenre = iter->first;
        auto indexMap = genreIndexMap[nowGenre];
        
        vector<pair<string, int>> indexVec(indexMap.begin(), indexMap.end());
        sort(indexVec.begin(), indexVec.end(), compare);
        
        int maxNum = 2; // 한 장르에서 최대 2곡
        
        for(int i=0; i<maxNum && i<indexVec.size(); i++) {
            int idx = indexVec[i].first.find("/");
            answer.push_back(stoi(indexVec[i].first.substr(idx+1))); // "/" 이후의 숫자만 추출
        }
    }
    
    
    return answer;
}

 

 

결과