[1일 1알고] 베스트앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

자료구조를 활용하는 문제입니다.

 

비효율적으로 풀더라도 정답 자체에 대한 문제는 없겠지만 그래도 효율적으로 풀기 위한 노력을 하는 것이 중요하겠죠

 

// most streaming 노래를 두 개씩 모아 베스트 앨범 출시
// 노래는 고유번호로 구분
// 우선 수록 기준
// 1. 속한 노래가 많이 재생된 장르 
// 2. 장르 내에서 많이 재생된 노래
// 3. 장르 내에서 재생 수가 같다면 고유 번호가 낮은 노래

 

의 조건을 지켜야합니다.

 

그렇다면 많이 재생된 장르를 찾기 위한 방법, 장르 내에서 조건에 맞추기 위한 방법이 필요합니다.

---

struct Music
{
    int total;
    vector<pair<int, int>> v_play_num;
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int N = genres.size();
    unordered_map<string, Music> streamingMap;
    for (int i = 0; i < N; ++i)
    {
        if (streamingMap.find(genres[i]) == streamingMap.end())
        {
            Music music;
            streamingMap.insert({ genres[i], music });
            streamingMap[genres[i]].total = plays[i];
            streamingMap[genres[i]].v_play_num.push_back({ plays[i], i});
        }
        else
        {
            streamingMap[genres[i]].total += plays[i];
            streamingMap[genres[i]].v_play_num.push_back({ plays[i], i });
        }

    }
    vector<pair<int, string>> most_stream;
    for (auto& stream : streamingMap)
    {
        most_stream.push_back({ stream.second.total, stream.first });
        sort(stream.second.v_play_num.begin(), stream.second.v_play_num.end(),
            [](const pair<int, int>& a, const pair<int, int>& b)
        {
            if (a.first != b.first)
                return a.first > b.first;  

            return a.second < b.second;     
        });
    }

    sort(most_stream.rbegin(), most_stream.rend());

    for (auto stream : most_stream)
    {
        string& genre = stream.second;
        int idx = 0;
        for (auto play_num : streamingMap[genre].v_play_num)
        {
            answer.push_back(play_num.second);
            ++idx;
            if (idx == 2)
                break;
        }
    }
    return answer;
}

 

따라서 장르 이름을 통해 노래에 대한 정보를 찾을 수 있는 map과 전체 재생 횟수를 통해 장르를 찾을 수 있는 vector를 사용합니다.

 

장르에 대한 정보는 genres와 plays를 순회하며 계속 찾아야하기 때문에 map으로 했지만 재생 회수는 이미 있는 정보를 통해 정렬만 하면 되기 때문에 vector를 사용했습니다.

 

그리고 장르 내(map)에서는 정렬 기준에 따라 정렬시키고 이를 통해 값을 도출했습니다.