스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
각 장르를 기준으로 플레이 타임을 저장한 후, 플레이 타임이 많은 순서대로 2곡씩 넣어주면 해결되는 문제.
문제 풀이
우선순위 큐와 map 을 사용해서 풀이했다.
두가지의 map을 설정하여 하나는 플레이타임과 장르를 저장하고, 하나는 장르를 key로 사용해, 우선순위큐를 value로 갖는 map 을 구성했다.
vector에 플레이타임과 장르를 저장해 주고, 정렬해준 다음, 순서대로 두 곡씩 넣어줬다.
C++ STL에 있는 priority_queue는 max heap 이여서 우선순위 큐에 넣어줄 때, 음수로 변환해 넣어줬다.
코드
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
vector<pair<int, string>> genre_cnt;
map<string, int> genre_play_cnt;
map<string, priority_queue<pair<int, int>>> songs;
for (int i=0; i<genres.size(); i++) {
genre_play_cnt[genres[i]] += plays[i];
songs[genres[i]].push(make_pair(plays[i], -i));
}
for (auto it = genre_play_cnt.begin(); it!=genre_play_cnt.end(); it++) {
genre_cnt.push_back(make_pair(it->second, it->first));
}
sort(genre_cnt.begin(), genre_cnt.end());
reverse(genre_cnt.begin(), genre_cnt.end());
for (int i=0; i < genre_cnt.size(); i++) {
string gen_name = genre_cnt[i].second;
int cnt = 0, len = songs[gen_name].size();
for (int j=0; j<len; j++) {
answer.push_back(-songs[gen_name].top().second);
songs[gen_name].pop();
cnt += 1;
if (cnt == 2) break;
}
}
return answer;
}
회고
마음만 급하니까 될것도 잘 안된다. 급한 상황에서도 침착함을 유지할 수 있는 방법을 찾아놔야 할 것 같다.
처음에 하나의 변수에 전부 처리하려고 해서 복잡하게 꼬였었는데, 그냥 두개로 나눠서 하니까 코드도 훨씬 간결해지고 풀이도 더 수월해졌다. db 에서 역정규화 하는 것 마냥 이런부분들도 생각을 해봐야 할듯.
map 이 아니라 unordered_map 을 사용했으면 메모리 관리와 시간쪽에서 좀 더 이득을 볼 수 있었을 것 같다.
