• 해시 알고리즘 문제 : 프로그래머스 LEVEL 3(베스트 앨범)) image - 사용 언어 : C++ - 해결 날짜 : 2021-02-18

    **- 해결 방법** :

    - 처음에 문제를 잘 못 이해하여 가장 많이 재생된 노래 두 개씩을 모아 총 4개만
    베스트 앨범에 수록하는 것 인줄 알았다.
    그리고 하나의 map에 고유 번호와 재생된 횟수를 담는 법을 고민하는데 시간이 좀 걸렸다.

    - 우선 각 장르별 재생 횟수를 담을 m1(총 합), 각 장르별 고유번호와
    재생 횟수를 담을 m2 map을 선언하여 for문을 돌며 추가해주었다.
    그 후 노래가 가장 많이 재생된 장르를 찾아 그 장르 내에서 많이 재생된 노래
    최대 2개를 찾아 answer vector에 추가하는 과정을 통해 문제를 해결하였다.
    만일 두개의 노래를 찾는 중 노래가 없거나 한 개 밖에 없는 경우라면 break로
    다음 장르로 넘어가도록 하였다.
    베스트 앨범에 들어갈 노래를 찾아 고유번호를 추가 후 삭제하고, 마찬가지로
    최대 2개씩 노래를 추가한 앨범은 erase 함수로 삭제하였다.


- 코드

```c++

    #include #include #include <map>

    using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> m1;
    map<string, map<int, int>> m2;

    //각 장르별 재생 횟수를 담고, 각 장르별 고유번호와 재생횟수를 담음
    for(int i = 0; i<genres.size(); i++){
        m1[genres[i]] += plays[i];
        m2[genres[i]][i] = plays[i];
    }

    //노래가 가장 많이 재생된 장르를 찾아 그 장르 내에서 많이 재생된 노래(최대 2개)를 찾아 answer에 추가
    while(m1.size() > 0){
        string genre;
        int max = 0;
        for(auto temp : m1){
            //현재 노래가 가장 많이 재생된 장르를 찾음
            if(temp.second > max){
                max = temp.second;
                genre = temp.first;
            }
        }

        for(int i = 0; i<2; i++){
            int numOfPlays = 0;
            int index = -1;
            for(auto temp : m2[genre]){
                //장르 내에서 많이 재생된 노래를 찾음
                if(temp.second > numOfPlays){
                    numOfPlays = temp.second;
                    index = temp.first;
                }
            }
            //두 개의 노래를 찾는 중 노래가 없거나 한 개뿐이라면 break
            if(index < 0) break;

            //베스트 앨범에 들어갈 노래의 고유번호를 추가 후 삭제
            answer.push_back(index);
            m2[genre].erase(index);
        }
        //베스트 앨범에 들어갈 노래를 다 추가한 장르는 삭제
        m1.erase(genre);
    }

    return answer;
}
```