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

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

프로그래머스

https://usowelcome.tistory.com/57

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

 

예전에 풀어봤던 문제다!

기억이 가물가물해서 이번에 다시 풀었는데... 흠.. 일단 둘 다 풀리긴 한다!

 

이번에는 각 장르별 노래들을 비교하기 위해, map안의 value를 vector로 만들어줬다.

=> 전체 플레이 횟수별로 장르를 정렬했으면, 장르마다 딸린 vector를 정렬해서 거기에서 가장 높은거 두개만 뽑아오면 된다는 생각!

 

실행시간도 비교해봤는데 다이나믹하게 차이가 나진 않고.....

 

근데 만약 이런 비슷한 문제를 또 풀어야 한다면, 이번에 푼 방식처럼 할것같긴하다.

왜냐면.. map으로 데이터를 내 입맛대로 가공해두니까 전체적으로 어디서 뭘 뽑아와야 하는지 오래 고민하지 않는 느낌?

 

메모리 사용량에 큰 차이가 있지도 않고 말이다! 물론 양이 많아지면 지금 푼 방식이 메모리 사용량은 더 많을것같긴한데,, 알아보기 편한게 좋은거 아닌가??ㅎ

---

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

using namespace std;

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

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

map<string, vector<pair<int, int>>> mymap;  // {index, plays}
map<string, int> totalplay;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    for(int i = 0; i<genres.size(); i++){
        mymap[genres[i]].push_back({i, plays[i]});
        if(totalplay.find(genres[i]) == totalplay.end()){
            // 없음
            totalplay[genres[i]] = plays[i];
        }else{
            totalplay[genres[i]] += plays[i];
        }
    }
    
    vector<pair<string, int>> vecplays(totalplay.begin(), totalplay.end());
    sort(vecplays.begin(), vecplays.end(), comp);
    
    for(int i = 0; i<vecplays.size(); i++){
        sort(mymap[vecplays[i].first].begin(), mymap[vecplays[i].first].end(), comp2);
        for(int j = 0; j<2; j++){
            if(j >= (int)mymap[vecplays[i].first].size()){
                break;
            }
            answer.push_back(mymap[vecplays[i].first][j].first);
        }
    }
    
    return answer;
}