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

베스트앨범

문제 링크

베스트앨범

분석

노래를 수록하는 기준은 다음과 같습니다.

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

genres는 노래의 장르를 가리키며, genres[i]는 고유 번호가 i인 노래 장르입니다.
plays는 재생 횟수를 가리키며, plays[i]는 고유 번호가 i인 노래가 재생된 횟수입니다.

genres와 plays의 크기는 같습니다.
고유 번호는 배열의 인덱스와 같습니다.

베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 반환해야합니다.

풀이

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    // 각 장르에 해당하는 노래의 고유 번호와 재생횟수를 저장
    unordered_map<string, vector<pair<int, int>>> genrePlayList;
    // 각 장르의 총 재생 횟수를 저장
    unordered_map<string, int> genrePlayCount;
    
    // 장르별로 노래 정보와 총 재생 횟수를 저장
    for (int i = 0; i < genres.size(); ++i)
    {
        genrePlayList[genres[i]].push_back({i, plays[i]});
        genrePlayCount[genres[i]] += plays[i];
    }
    
    // 장르의 총 재생 횟수를 내림차순으로 정렬
    vector<pair<string, int>> sortGenre(genrePlayCount.begin(), genrePlayCount.end());
    sort(sortGenre.begin(), sortGenre.end(),
        [](const pair<string, int>& a, const pair<string, int> b)
         {
             return a.second > b.second;
         });
    
    // 내림차순된 장르의 총 재생 횟수를 순회한다.
    for (const auto& e : sortGenre)
    {
        // 현재 장르의 이름
        const string& genre = e.first;
        // 현재 장르에 해당하는 노래들의 고유 번호와 재생 횟수 목록
        auto& songs = genrePlayList[genre];
        
        // 현재 장르에 해당하는 노래들을 재생 횟수 기준으로 내림차순 정렬한다.
        // 재생 횟수가 같은 경우 고유 번호를 기준으로 오름차순 정렬한다.
        sort(songs.begin(), songs.end(),
            [](const pair<int, int>& a, const pair<int, int>& b)
             {
                if (a.second == b.second) 
                {
                    return a.first < b.first;
                }
                 return a.second > b.second;
             });
        
        // 현재 장르에서 재생 횟수가 가장 많은 2곡을 반환 값에 저장한다.
        for (int i = 0; i < songs.size(); ++i)
        {
            if (i >= 2)
            {
                break;
            }
            
            answer.push_back(songs[i].first);
        }
    }
    
    return answer;
}

1. 장르별 총 재생 횟수가 많은 순서로 장르를 정렬합니다.
2. 각 장르 내에서 재생 횟수가 많은 노래를 두 곡까지만 선택합니다.
3. 재생 횟수가 동일한 경우, 고유 번호가 낮은 노래를 우선합니다.

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 장르별로 노래 정보와 총 재생 횟수를 저장하는 반복문 $O(n)$
  • n은 노래 수
• 장르의 총 재생 횟수를 내림차순으로 정렬하는 함수 $O(g \ log \ g)$
  • g는 장르 수
• 장르의 총 재생 횟수를 순회하는 반복문 $O(g)$
• 노래들을 재생 횟수 기준으로 내림차순 정렬하는 함수 $O(n \ log \ n)$
  • 정렬을 g번 하지만, 대상이 쪼개진 n개의 부분합이기 때문에 해당 시간 복잡도가 나온다.
• $O(n) + O(g \ log \ g) + O(n \ log \ n)$

공간 복잡도는 $O(n)$입니다.

• 각 장르에 해당하는 노래의 고유 번호와 재생횟수를 저장하는 genrePlayList $O(n)$
• 각 장르의 총 재생 횟수를 저장하는 genrePlayCount $O(g)$
• 장르의 총 재생 횟수를 내림차순으로 정렬한 결과를 저장하는 sortGenre $O(g)$
• 반환 값을 저장하는 answer $O(g)$
• $O(n) + O(g) + O(g) + O(g)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 3.62MB)
테스트 4 〉 통과 (0.01ms, 4.27MB)
테스트 5 〉 통과 (0.03ms, 4.21MB)
테스트 6 〉 통과 (0.04ms, 4.2MB)
테스트 7 〉 통과 (0.02ms, 4.16MB)
테스트 8 〉 통과 (0.02ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.04ms, 3.71MB)
테스트 11 〉 통과 (0.03ms, 4.13MB)
테스트 12 〉 통과 (0.03ms, 3.67MB)
테스트 13 〉 통과 (0.03ms, 4.21MB)
테스트 14 〉 통과 (0.04ms, 4.21MB)
테스트 15 〉 통과 (0.02ms, 4.21MB)