[프로그래머스 Lv.3 / C++] Day63. 베스트앨범

2024. 08. 05 - 코딩테스트 스터디 Day63

 
 

01. 문제 설명

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

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

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

 
 

02. 제한사항

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

 
 

03. 입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

 

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

 
 

04. 풀이 및 답

코드 전문

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool cmpMusic(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

bool cmpTotal(pair<string, int> a, 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> totalMap;
    unordered_map<string, vector<pair<int, int>>> musicMap;     // 고유번호, 재생 횟수 저장
    
    for (int i = 0; i < genres.size(); i++) {
        totalMap[genres[i]] += plays[i];    // 장르별 재생 횟수
        musicMap[genres[i]].push_back(make_pair(i, plays[i]));   // 노래별 재생 횟수 (고유번호, 재생 횟수)
    }
    
    for (auto &m : musicMap) {
        sort(m.second.begin(), m.second.end(), cmpMusic);
    }
    
    vector<pair<string, int>> sortedTotalMap(totalMap.begin(), totalMap.end());
    sort(sortedTotalMap.begin(), sortedTotalMap.end(), cmpTotal);
    
    for (auto s : sortedTotalMap) {
        string name = s.first;
        int count = 0;
        
        for (auto &m : musicMap[name]) {
            answer.push_back(m.first);
            if (++count == 2) break;
        }
    }
    
    return answer;
}

위 코드는 장르별 총 재생 횟수와 각 노래의 고유 번호와 재생 횟수를 담을 해시 맵을 두 개 선언한다.
장르별 총 재생 횟수를 계산하고, 각 노래의 고유 번호와 재생 횟수를 구해 각 해시 맵에 장르별을 key로 선정하여 저장한다.
장르별 총 재생 횟수에 따라, 그리고 각 노래의 재생 횟수에 따라 각 해시 맵을 정렬하고, 올바른 순서대로 2곡씩 answer에 저장한다.
 
코드가 기니까 자세한 설명은 나눠서 적도록 하겠다.
 
1. 해시 맵 선언

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    unordered_map<string, int> totalMap;
    unordered_map<string, vector<pair<int, int>>> musicMap;     // 고유번호, 재생 횟수 저장

장르별 총 재생 횟수를 구하기 위한 totalMap과 각 노래의 고유 번호, 재생 횟수를 저장할 musicMap을 선언했다.
totalMap은 string 타입인 장르를 key로, int 타입인 한 장르에 해당하는 모든 노래의 총 재생 횟수를 value로 갖는다.
musicMap은 string 타입은 장르를 key로 가지며, pair<int, int> 쌍의 벡터를 value 값으로 가지는데, 이 pair<int, int> 형의 벡터에는 각각 노래의 고유 번호와 재생 횟수가 들어갈 것이다.
 
2. 장르별 재생 횟수 및 노래별 재생 횟수 구하기

    for (int i = 0; i < genres.size(); i++) {
        totalMap[genres[i]] += plays[i];    // 장르별 재생 횟수
        musicMap[genres[i]].push_back(make_pair(i, plays[i]));   // 노래별 재생 횟수 (고유번호, 재생 횟수)
    }

같은 장르를 key로 갖는 재생 횟수들을 totalMap의 value에 더해준다.
같은 장르를 key로 갖는 노래들의 고유 번호와 재생 횟수 쌍을 벡터에 저장해 준다.
 
3. 각 노래의 재생 횟수 기반으로 고유 번호 정렬

    for (auto &m : musicMap) {
        sort(m.second.begin(), m.second.end(), cmpMusic);
    }

각 장르(key)에 대한 값들을 재생 횟수(=m.second)를 기반으로 내림차순 정렬한다.
 
cmpMusic 함수

bool cmpMusic(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

 
 
4. 장르별 총 재생 횟수 정렬

    vector<pair<string, int>> sortedTotalMap(totalMap.begin(), totalMap.end());
    sort(sortedTotalMap.begin(), sortedTotalMap.end(), cmpTotal);

unordered_map은 내부적으로 순서를 보장하지 않기 때문에 정렬하기 위해서는 별도의 벡터에 데이터를 옮겨줘야 한다.
따라서 sortedTotalMap이라는 벡터에 totalMap의 데이터를 모두 옮긴 뒤, 내림차순으로 정렬한다.
 
cmpTotal 함수

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

 
 
5. 고유번호 순서대로 리턴하기

    for (auto s : sortedTotalMap) {
        string name = s.first;
        int count = 0;
        
        for (auto &m : musicMap[name]) {
            answer.push_back(m.first);
            if (++count == 2) break;
        }
    }
    
    return answer;
}

장르별 총 재생 횟수에 따라, 그리고 각 노래의 재생 횟수에 따라 정렬을 마쳤기 때문에 이제 벡터에 순서대로 저장만 해주면 된다.
 
장르별 총 재생 횟수가 높은 장르부터 차례로 해당 장르 속 노래의 고유 번호(m.first)를 answer에 저장한다.
문제에서 2곡씩만 저장한다고 했기 때문에 count가 2가 되면 반복문을 빠져나간다.
 
 

정답!

---

역시 레벨 3 문제는 어렵닷
 
 
참고한 게시글

[프로그래머스 Level_3 / C++] 베스트앨범