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

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.

입출력 예

Solution

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

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

bool compMusic(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, int> music;
    unordered_map<string, vector<pair<int, int>>> musicData;
    int N = genres.size();
    for(int i = 0; i < N; i++){
        music[genres[i]] += plays[i];
        musicData[genres[i]].push_back({plays[i], i});
    }
    vector<pair<string, int>> musicVector;
    musicVector.assign(music.begin(), music.end());
    sort(musicVector.begin(), musicVector.end(), comp);

    for(int i = 0; i < musicVector.size(); i++){
        string genre = musicVector[i].first;
        sort(musicData[genre].begin(), musicData[genre].end(), compMusic);
        for(int j = 0; (j < musicData[genre].size()) && (j < 2) ; j++){
            answer.push_back(musicData[genre][j].second);
        }
    }
    return answer;
}

여러 방법들이 있다. map을 쓰는 방법이 있고 unordered map을 쓰는 방법이있다. 나는 unordered_map을 활용해서 내부에 vector를 집어넣어서 데이터를 저장하는 방식을 써 보았다.

unordered_map<string, int> music;
unordered_map<string, vector<pair<int, int>>> musicData;
int N = genres.size();
for(int i = 0; i < N; i++){
    music[genres[i]] += plays[i];
    musicData[genres[i]].push_back({plays[i], i});
}

music은 특정 장르가 얼마나 재생되었는 지 저장하는 unordered_map, musicData는 해당 장르의 데이터를 분류해서 vector에 저장하는 unordered_map이다. 우리가 hashing을 쓰는 이유가 뭘 지 가만히 생각해보았다. 주로 데이터를 어떠한 기준으로 분류하는 데 쓰지 않을까?

vector<pair<string, int>> musicVector;
musicVector.assign(music.begin(), music.end());
sort(musicVector.begin(), musicVector.end(), comp);

music data를 따로 분리해서 오름차순으로 정렬해둔다. 어떤 장르가 가장 많이 출력되었는 지 확인하려는 목적이다.

for(int i = 0; i < musicVector.size(); i++){
    string genre = musicVector[i].first;
    sort(musicData[genre].begin(), musicData[genre].end(), compMusic);
    for(int j = 0; (j < musicData[genre].size()) && (j < 2) ; j++){
        answer.push_back(musicData[genre][j].second);
    }
}
return answer;

그 후 각각 장르마다 unordered_map 내의 vector를 정렬한 후 2번간 반복하며 데이터를 answer에 집어넣는다. 간단하다. 단 한 장르마다 2개씩 플레이리스트를 뽑아낼 것이기 때문에 반복문에 조건을 추가한다. 처음에는 if문으로 처리했으나 굳이 그렇게 하지 않아도 되었다.

Level3 이라서 어떻게 구현해야하는 지를 고민했어야 했던 문제였다. map 내에 vector를 집어넣는 방식은 약간 무식해보일 지는 몰라도 엄연히 데이터를 처리하는 방식이고 오히려 이상하게 구현하는 것 보다는 확실하게 문제를 해결할 수 있었다고 생각한다.