https://school.programmers.co.kr/learn/courses/30/lessons/42579
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
스트리밍 사이트에서 장르별로 가장 많이 재생된 노래를 모아 베스트 앨범을 출시하려고 합니다. 각 노래는 고유 번호로 구분되며, 베스트 앨범에 수록할 노래를 선택하는 기준은 다음과 같습니다:
- 장르별 총 재생 횟수가 많은 장르부터 수록합니다.
- 각 장르 내에서 재생 횟수가 많은 노래를 먼저 수록합니다.
- 재생 횟수가 같은 경우, 고유 번호가 낮은 노래를 먼저 수록합니다.
이 문제는 genres와 plays라는 두 개의 배열을 기반으로, 주어진 조건에 맞게 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 반환하는 함수를 구현해주세요.
풀이 방법
문제를 처음 접했을 때 정렬이 핵심이라는 것을 알았지만, 어떻게 정렬해야 할지 고민을 많이 했습니다.
장르별 총 재생 횟수를 기준으로 가장 많이 듣는 장르 순서를 정한 뒤, 각 장르 내에서 가장 많이 플레이된 노래를 우선적으로 정렬해야 했기 때문에, 두 개의 custom sort 함수를 만들었습니다.
- cmp_genre : 장르별 총 재생 횟수를 기준으로 내림차순 정렬.
- cmp_genre_index : 장르 내 곡들의 재생 횟수를 기준으로 내림차순, 재생 횟수가 같을 경우 고유 번호 오름차순으로 정렬.
또한, 두 개의 unordered_map 자료구조와 하나의 정렬을 위한 vector 자료구조를 선언했습니다.
- unordered_map<string, int>: 각 장르의 총 재생 횟수를 저장.
- unordered_map<string, vector<pair<int, int>>>: 각 장르 내의 곡 정보(재생 횟수와 고유 번호)를 저장.
- vector<pair<string, int>>: 장르별 총 재생 횟수를 정렬하기 위해 사용.
정렬에 익숙하시다면 풀어볼만한 문제라고 생각합니다.
풀이 코드
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string,int> total_listening;
unordered_map<string, vector<pair<int, int>>> genre_index;
bool cmp_genre(const pair<string, int>& a, const pair<string, int>& b) {
return a.second > b.second;
}
bool cmp_genre_index(const pair<int, int>& a, const pair<int, int>& b) {
if(a.first == b.first) return a.second < b.second;
return a.first > b.first;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
for(int i=0; i<genres.size(); i++){
total_listening[genres[i]] += plays[i];
genre_index[genres[i]].push_back({plays[i],i});
}
vector<pair<string,int>> sorted_genre;
for(auto& iter : total_listening){
sorted_genre.push_back({iter.first, iter.second});
}
sort(sorted_genre.begin(), sorted_genre.end(), cmp_genre);
for(auto& iter : genre_index){
sort(iter.second.begin(), iter.second.end(), cmp_genre_index);
}
for(int i=0; i<sorted_genre.size(); i++){
string curr_genre = sorted_genre[i].first;
if(genre_index[curr_genre].size() == 1){
answer.push_back(genre_index[curr_genre][0].second);
}
else{
answer.push_back(genre_index[curr_genre][0].second);
answer.push_back(genre_index[curr_genre][1].second);
}
}
return answer;
}
'Algorithm > Programmers' 카테고리의 다른 글
[프로그래머스] Lv.1 가장 많이 받은 선물 c++ (0) | 2025.01.22 |
---|---|
[프로그래머스] Lv.2 기능개발 c++ (0) | 2025.01.21 |
[프로그래머스] Lv.1 문자열 나누기 c++ (0) | 2025.01.21 |
[프로그래머스] Lv.1 신고 결과 받기 c++ (1) | 2025.01.20 |
[프로그래머스] Lv.1 달리기 경주 c++ (0) | 2025.01.20 |