해시_베스트앨범_프로그래머스42579

About this offer

level3 문제 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다. genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다. 장르 종류는 100개 미만입니다. 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다. 모든 장르는 재생된 횟수가 다릅니다. 코드 #include <string> #include <vector> #include <map> #include <unordered_map> #include <algorithm> using namespace std; // 장르 정렬을 위한 커스텀 비교 함수 (내림차순) bool cmpGenres(const pair<string, int>& a, const pair<string, int>& b) { return a.second > b.second; } bool cmpSongs (pair<int,int>& a,pair<int,int>& b ){ if(a.first==b.first){ return a.second<b.second; }return a.first>b.first; } /* 장르별로 랭크 매기기 장르 / 재생횟수 / 번호, pair, unordered_map 활용 cmp을 활용해서 장르별로 순서 정렬하기 정렬한 순서대로 answer에 집어넣기 */ vector<int> solution(vector<string> genres, vector<int> plays) { vector<int> answer; // 장르별 총 재생 횟수 (장르, 총 재생수) unordered_map<string, int> genre_total_play; // 장르별 노래 목록 (장르 -> vector<{재생 횟수, 고유 번호}>) unordered_map<string, vector<pair<int, int>>> genre_songs; // 1. 해시맵 데이터 수집 for (int i = 0; i < genres.size(); i++) { //map 초기화할 필요없이 바로 더하기 genre_total_play[genres[i]] += plays[i]; //순회 돌면서 play, id 저장 genre_songs[genres[i]].push_back({plays[i], i}); } // 2. 장르를 총 재생 횟수 기준으로 정렬하기 위해 vector로 변환 vector<pair<string,int>> sorted_genres(genre_total_play.begin(),genre_total_play.end()); //내림차순 정렬 sort(sorted_genres.begin(),sorted_genres.end(),cmpGenres); //<pair<string,int>> for(auto genre_pair:sorted_genres){ string current_genre = genre_pair.first; //임시 배열 생성 auto& songs = genre_songs[current_genre]; sort(songs.begin(),songs.end(),cmpSongs); //가장 많이 재생된 노래를 두 개씩 모아 for(int i=0;i<songs.size() && i<2 ;i++){ answer.push_back(songs[i].second); } } return answer; } 이번 문제에서의 테크닉 unordered_map 에 값을 집어넣는 방법 // 장르별 총 재생 횟수 (장르, 총 재생수) unordered_map<string, int> genre_total_play; // 장르별 노래 목록 (장르 -> vector<{재생 횟수, 고유 번호}>) unordered_map<string, vector<pair<int, int>>> genre_songs; // 1. 해시맵 데이터 수집 for (int i = 0; i < genres.size(); i++) { //map 초기화할 필요없이 바로 더하기 genre_total_play[genres[i]] += plays[i]; //순회 돌면서 play, id 저장 genre_songs[genres[i]].push_back({plays[i], i}); } map을 활용할때 내용값을 넣을때 기억이 잘 안났는데, 별도의 초기화 없이 바로 값을 넣는것과, vector을 다루는 경우 push_back을 활용한다. map -> vector 전환 // 장르별 총 재생 횟수 (장르, 총 재생수) unordered_map<string, int> genre_total_play; // genre_total_play(unordered_map)의 시작과 끝 이터레이터를 넘겨서 vector 생성 vector<pair<string, int>> sorted_genres(genre_total_play.begin(), genre_total_play.end()); <string,int>형식의 map을 바로 vector로 전환하는 방식, 정렬을 위해 필요한 과정이다. 이번 문제가 어려웠던 이유 복합적으로 자료구조를 활용해야 했다. 또한, 자료구조간의 변환이 일어났다. 특히 이미 정렬되어있는 vector을 활용해서, 별도로 저장해놓은 unordered_map을 탐색하는 방식은 생각해보지 못했다. vector의 값을 활용해서, 임의 벡터를 활용해 특정 벡터의 값을 또 정렬하고 활용할 생각을 잘 못했다.