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

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

문제풀이

• 2가지 map이 필요하다.

  1. map <string 장르, int 재생횟수> songMap : 각 장르마다 재생횟수를 누적하여 내림차순으로 정렬한다.
  2. map <string 장르, vector<Song>> genreCntMap : 각 장르마다 속한 노래를 Song 구조체 벡터에 push한다.

• Song 구조체

  • 재생횟수와 고유번호를 필드로 가진다.
  • 재생횟수로 내림차순 정렬, 고유번호로 오름차순 정렬 되도록 설정

• genreCntMap 와 songMap 모두 기준에 맞게 정렬한 후 genreCntMap 에서 장르를 하나씩 꺼내면서 songMap을 이용해 해당 장르의 상위 노래 2개씩을 answer에 추가해주면 된다.

새로 배운 것

✨map을 value 기준으로 정렬하는 법

• map은 기본적으로 key값 기준으로 오름차순으로 정렬된다. 따라서 value 기준으로 정렬하려면 따로 방법이 있음!

1. map을 vector로 이동

• 정렬할 map을 같은 데이터형의 vector에 초기화 해주기

//1. 선언과 따로 초기화
map<string,int> genreCntMap;
vector<pair<string,int>> genreCntVector;

genreCntVector.assign(genreCntMap.begin(), genreCntMap.end());



//2. 선언과 동시에 초기화
map<string,int> genreCntMap;
vetor<pair<string,int>>genreCntVector(genreCntMap.begin(), genreCntMap.end());

2. 정렬 함수

bool compareGenreCntMap(pair<string,int> a, pair<string,int> b){
    return a.second > b.second; // 재생횟수를 기준으로 내림차순으로 정렬
}

3. 정렬

    sort(genreCntVector.begin(),genreCntVector.end(),compareGenreCntMap);

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct Song{
    int playCnt; int Id;
    Song(int a, int b){playCnt=a;Id=b;}
    bool operator<(const Song &b)const{
        if(playCnt!=b.playCnt) return playCnt>b.playCnt; //재생횟수 내림차순
        return Id<b.Id; //고유번호 오름차순
    }
};
bool compareGenreCntMap(pair<string,int> a, pair<string,int> b){
    return a.second > b.second; // 재생횟수를 기준으로 내림차순으로 정렬
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, vector<Song>> songMap; //<장르, vector(재생횟수,고유번호)>
    map<string,int> genreCntMap; //<장르, 재생횟수>

    for(int i=0;i<genres.size();i++){
        songMap[genres[i]].push_back(Song(plays[i],i)); 
        genreCntMap[genres[i]]+=plays[i];
    }
    
    //1. songMap의 각 key(장르)마다 value인 Song들을 정렬
    for(auto it=songMap.begin();it!=songMap.end();it++){
        sort((it->second).begin(), (it->second).end());
    }

    //2. genreCntMap의 value인 재생 횟수를 내림차순 정렬
    vector<pair<string,int>> genreCntVector(genreCntMap.begin(), genreCntMap.end()); //정렬하기 위해 map을 vecotr로 이동
    sort(genreCntVector.begin(),genreCntVector.end(),compareGenreCntMap);

    for(int i=0;i<genreCntVector.size();i++){
        string genre=genreCntVector[i].first; //이 장르를 가지고.. SongMap에서 찾아서 고유번호 찾기!

        for(int j=0;j<songMap[genre].size();j++){
            if(j>=2) break; //2개 까지
            answer.push_back(songMap[genre][j].Id); // ✨value vector의 j번째 원소의 Id
        }
    }
    return answer;
}