[Algorithm] 프로그래머스 베스트 앨범 - C++, map, unordered_map

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

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

bool cmp(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;

    unordered_map<string, int> genresTimes;
    unordered_map<string, map<int, int>> musicInfo; // genres, index, playtimes

    // make unordered map
    for(int i = 0; i < genres.size(); i++){
        genresTimes[genres[i]] += plays[i];
        musicInfo[genres[i]][i] = plays[i];
    } 

    // find most played genres
    // and find most played music in that genres

    // 1. sort genres by played time
    vector<pair<string, int>> genresPlayTimes(genresTimes.begin(), genresTimes.end());
    sort(genresPlayTimes.begin(), genresPlayTimes.end(), cmp);

    for(int i = 0; i < genresPlayTimes.size(); i++){
        // search most played genres
        string curGenre = genresPlayTimes[i].first;
        
        // find two music in this genres
        for(int genCount = 0; genCount < 2; genCount++){
            int playTime = -1, index = -1;
            for(auto music : musicInfo[curGenre]){
                if(playTime < music.second){
                    playTime = music.second;
                    index = music.first;
                }
            }

            if(index == -1) continue;

            answer.push_back(index);
            musicInfo[curGenre].erase(index);
        }
    }

    return answer;
}

---

 이번에는 생각할게 좀 있는 문제였습니다.

 

 일단 unordered_map 을 2개 선언을 해 주는데 역할은 아래와 같습니다.

genresTimes	장르별 플레이타임 횟수를 저장
musicInfo	장르 내 음악들의 정보를 저장

 이중 musicInfo 안에는 unordered_map이 아닌 map이 들어가 있는데 이는 map 은 들어가면 key값을 기준으로 자동 정렬이 되어 이후 출력에서 인덱스가 빠른 순으로 보낼 수 있기 때문입니다.

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

// 1. sort genres by played time
    vector<pair<string, int>> genresPlayTimes(genresTimes.begin(), genresTimes.end());
    sort(genresPlayTimes.begin(), genresPlayTimes.end(), cmp);

 이후 genresTimes에 모든 데이터를 넣어둔 뒤 장르들을 전부 vector에 넣은 뒤 정렬을 해 줍니다. cmp 함수에서 왼쪽이 더 큰 경우로 해서 높은 값이 먼저 오게 오름차순으로 해 주시면 됩니다.

    for(int i = 0; i < genresPlayTimes.size(); i++){
        // search most played genres
        string curGenre = genresPlayTimes[i].first;
        
        // find two music in this genres
        for(int genCount = 0; genCount < 2; genCount++){
            int playTime = -1, index = -1;
            for(auto music : musicInfo[curGenre]){
                if(playTime < music.second){
                    playTime = music.second;
                    index = music.first;
                }
            }

            if(index == -1) continue;

            answer.push_back(index);
            musicInfo[curGenre].erase(index);
        }
    }

 이후 각 장르에서 가장 많이 들린 노래를 골라야 하는데 여기서 주의할 점이 각 장르에서 2개만 뽑아야 하는 것, 장르에 노래가 1개면 1개만 삽입해야 하는 것, 같은 재생수라면 인덱스 번호순으로 해야 한다는 것입니다.

 위 주의점들을 처리하기 위해서 for문은 각 장르에서 2번만 돌게 했으며 노래가 1개인 경우는 index == -1 을 체크해 처리했습니다. (index 값이 변경되지 않았다면 해당 장르에 남은 곡이 없다는 뜻) 그리고 인덱스 번호순은 따로 정렬을 두지 않고 unordered_map안에 unordered_map 대신 map을 넣어서 처리했습니다.