[Level 3] 베스트 앨범 - 해시 | C++

[문제]

문제 설명

 

입출력 예시

문제 설명이 더 헷갈리게 만들어서 예제를 보고 풀었다. 문제는 간단하게 설명해보면 일단 장르와 플레이 횟수가 저장된 벡터가 인자로 주어지는데, 두 벡터의 각 요소는 쌍이다. 무슨 뜻이냐면, 위 예제에서 classic 장르의 어떤 곡의 플레이 횟수가 500, pop 장르의 어떤 곡의 플레이 횟수가 600 이런 식으로 곡의 장르와 플레이 횟수를 두 벡터에 나눠 저장해둔 것이다. 따라서 두 벡터는 크기가 동일하다. 한마디로 위 예제는 클래식 장르 3곡과 pop 장르 2곡이 담긴 리스트다. 

여기서 각 장르 내에서 가장 많이 플레이된 두 곡의 인덱스(고유번호)를 차례대로 배열에 담아 반환하는 것이 문제이다. 또한 가장 많이 플레이 된 장르 순으로 저장되어야 한다. 예를 들어 A 장르의 플레이 횟수 합이 100이고 B 장르의 플레이 횟수 합이 200이면 B 장르의 곡부터 저장한다.

[풀이]
우선 내가 설계한 방법은 다음과 같다. 우선 인자로 장르가 담긴 벡터 genres, 플레이 횟수가 담긴 벡터 plays가 주어진다.

1. 장르-인덱스(고유번호) 쌍을 벡터에 저장한다. (i.e. ["classic", 0], ["pop", 1], ...)
2. 장르-장르별 곡들의 플레이 횟수 합의 key-value쌍을 가지는 해시맵을 만든다. (i.e. ["classic", 1450], ["pop", 3100])
3. 2번의 해시맵의 key-value 쌍을 새로운 벡터에 모두 복사한다.
4. 3번의 벡터를 value(플레이 횟수의 합)를 기준으로 내림차순 정렬한다. 결과는 ["pop", 3100], ["classic", 1450]
5. 1번의 벡터를 plays[value]를 기준으로 내림차순 정렬한다. 즉 플레이 횟수가 높은 순으로 정렬되며, 결과는 ["pop", 4], ["classic", 3], ["pop", 1], ... 처럼 정렬된다. 
6. 5번의 벡터를 해시맵에 장르-벡터<인덱스> 쌍으로 저장한다. 즉 ["pop", {4, 1}], ["classic", {3, 0, 2}] 와 같이 저장된다.
7. 장르의 종류만큼 루프를 돌면서 4번의 벡터에 저장된 장르 순서를 이용하여 6번 해시맵의 value의 0,1번 째 인덱스 값을 결과 벡터에 차례로 추가한다.

설명이 애매해서 이해하기 힘들 수 있는데 간단히 결과만 말하면 다음과 같다.

vec: ["pop", 3100], ["classic", 1450] 처럼 플레이 횟수가 높은 장르순으로 정렬하고, 

map: ["pop", {4, 1}], ["classic", {3, 0, 2}] 처럼 장르 내의 곡들의 인덱스를 플레이 횟수가 높은 순으로 정렬하여 위 vec의 장르 순서대로 상위 2개의 인덱스들만 차례로 반환할 벡터에 추가하는 것이다. std::sort 함수가 N*logN의 시간 복잡도를 가지므로 해당 코드는 배열의 크기를 N으로 봤을 때, O(N*logN)의 시간 복잡도를 가진다.

[소스 코드]

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) 
{
    vector<int> answer;
    size_t size = genres.size();

    vector<std::pair<string, uint32_t>> genreIndex;
    unordered_map<string, uint32_t> sum;
    genreIndex.reserve(size);
    sum.reserve(100); // 장르 종류의 최대 개수
   
    for(size_t i = 0; i != size; ++i)
    {
        genreIndex.emplace_back(std::pair<string, uint32_t>(genres[i], i));
        sum[genres[i]] += plays[i];
    }
    
    // map의 장르-플레이 횟수의 합 쌍을 벡터에 복사 후 내림차순 정렬
    vector<std::pair<string, uint32_t>> sortedSum;
    sortedSum.reserve(sum.size());
    for(const auto& mypair : sum)
    {
        sortedSum.emplace_back(std::pair<string, uint32_t>(mypair.first, mypair.second));
    }
    
    std::sort(sortedSum.begin(), sortedSum.end(), 
              [](const std::pair<string, uint32_t>& a, const std::pair<string, uint32_t>& b) -> bool 
              { 
                  return a.second > b.second;
              });    
    
    
    // 장르 - 인덱스 쌍을 플레이 횟수를 기준으로 내림차순 정렬
    // i.e.
    // p 4
    // c 3
    // p 1
    // ...
    std::sort(genreIndex.begin(), genreIndex.end(), 
              [&](const std::pair<string, uint32_t>& a, const std::pair<string, uint32_t>& b) -> bool 
              { 
                  return plays[a.second] > plays[b.second];
              });
    
    
    // genreIndex 벡터를 해시맵에 key-value 쌍으로 저장
    // p [4, 1]
    // c [3, 0, 2]
    unordered_map<string, vector<uint32_t>> sortedGenreIndex;
    sortedGenreIndex.reserve(size);
    for(const auto& mypair : genreIndex)
    {
        sortedGenreIndex[mypair.first].push_back(mypair.second);
    }
    
    
    // sortedSum(벡터): 장르-플레이횟수 총합
    // sortedGenreIndex(맵): 장르-플레이횟수의 인덱스
    answer.reserve(2*sortedSum.size());
    for(const auto& mypair : sortedSum)
    {
        answer.push_back(sortedGenreIndex[mypair.first][0]);
        if(sortedGenreIndex[mypair.first].size() > 1)
            answer.push_back(sortedGenreIndex[mypair.first][1]);
    }
    
    return answer;
}