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

베스트앨범에 수록할 곡을 찾는 문제

이것 또한 최대 재생 장르를 찾는데까진 생각해냈지만 나머지 수록곡을 찾는 부분 구현을 어찌 해야 할 지 감이 안 와서 구글링이 필요했음...

 

---

문제의 조건

 

1. 노래의 장르를 담은 문자열 배열 genres, genres 배열의 각 원소들의 재생 횟수가 담긴 배열 plays가 주어짐

 

2. genres의 노래는 고유 번호로 구분되는데 고유번호는 genres 배열의 인덱스 번호임 

 

3. 노래 수록 기준은 다음과 같다. 

 

4. 위 기준대로 노래를 담았을 때 수록되는 인덱스 번호 순서를 리턴하기 

 

5. 필요한 것:

장르별 총 재생횟수

장르별 재생횟수와 인덱스 번호

 

장르별 총 재생횟수를 구해서 가장 많이 재생된 장르를 찾는다. 

찾은 장르로 가장 많이 재생된 고유번호 2개를 찾는다. 

answer 에 고유번호 2개 삽입 후 해당 장르는 삭제

장르별 총 재생횟수 배열이 빌 때까지 위 과정을 반복

 

---

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> playCounts; //장르별 총 재생횟수를 저장할 map
    map<string, map<int, int>> playMap; //장르별 고유번호와 재생횟수를 저장할 map

    for (int i = 0; genres.size() > i; i++)
    {
        //장르별 총 재생횟수를 구한다. 
        playCounts[genres[i]] += plays[i];
        //장르별 고유번호와 재생횟수를 저장한다. 
        playMap[genres[i]][i] = plays[i];
    }

    //장르별 총 재생횟수 map이 빌 때까지 반복 
    while (0 < playCounts.size())
    {
        //총 재생횟수(value값) 기준으로 장르별 총 재생횟수 map에서 최대값을 찾는다. 
        auto maxVal = max_element(playCounts.begin(), playCounts.end(),
        [](const pair<string, int>& a, const pair<string, int>& b)->bool{ return a.second < b.second;});
        //찾은 it를 이용하면 가장 많이 재생된 장르를 찾을 수 있다. 
        string maxGenre = maxVal->first;
        //베스트앨범에는 최대 두 곡까지만 수록되니까 2번 반복 
        for (int i = 0; 2 > i; i++)
        {
            int value = 0;
            int index = -1;
            for (auto m: playMap[maxGenre])
            {
                //map을 순회하면서 만약 더 큰 재생횟수를 찾으면 갱신한다. 
                if (value < m.second)
                {
                    value = m.second;
                    index = m.first;
                }
            }

            if (-1 == index) break; //-1이면 못 찾았으니까 반복문 탈출 
            //answer 배열에 삽입 
            answer.push_back(index);
            //최대값 원소 삭제 
            playMap[maxGenre].erase(index);
        }
        //수록곡 2개 찾기가 끝나면 해당 장르는 삭제 
        playCounts.erase(maxGenre);
    }

    return answer;
}

 

정답을 보고 쓰긴 했지만 코드를 해석하면서 블로그에 정리하니까 공부에 도움이 된다.