[프로그래머스] [C++] 베스트앨범 (map)

1. 문제

 

코딩테스트 연습 - 베스트앨범 | 프로그래머스 (programmers.co.kr)

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

 

 

2. map 

3개의 map으로 문제를 해결할 수 있다.

 

1. 장르 -> 해당 장르 노래의 모든 플레이 횟수

 

2. 장르 -> 해당 장르에서 플레이 횟수 가 가장 많은 두개의 노래 인덱스

 

3. 1 번을 뒤집은 map

 

 

장르 중에서 가장 큰 것을 먼저 선택해야하므로

      1번 map에서 3번 map 으로의 변환이 필요하다.

그 장르 속에서 가장 큰것 두개를 선택해야하므로

      2번 map 이 필요하다 

 

3번 map을 end부터 begin 까지 2에 대입하면서 모든 원소를 집어 넣으면 문제가 해결된다.

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
void pushBack(map<string, vector<int> >& mp, string& str, int idx, vector<int>& plays) {
    mp[str].push_back(idx);
 
    for(int i = mp[str].size() - 1; i >= 1; i--) {
        if(plays[mp[str][i]] > plays[mp[str][i-1]]) 
            swap(mp[str][i], mp[str][i-1]);
    }
 
    if(mp[str].size() == 3)
        mp[str].pop_back();
}
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
 
    map<string, int> genresToCount;
    map<string, vector<int> > genresToPlays;
    map<int, string> countToGenres;
 
    for(int i = 0; i < genres.size(); i++) {
        genresToCount[genres[i]] += plays[i];
        pushBack(genresToPlays, genres[i], i ,plays);
    }
 
    for(auto it = genresToCount.begin(); it != genresToCount.end(); it++) {
        countToGenres[it->second] = it->first;
    }
 
    for(auto it = countToGenres.end(); it-- != countToGenres.begin(); ) {
        for(int j = 0; j < genresToPlays[it->second].size(); j++)
            answer.push_back(genresToPlays[it->second][j]);
    }
    return answer;
}