[L3] 프로그래머스 베스트앨범 C++ 해시맵, 우선순위 큐

리뷰

프로그래머스

 

가장 많이 Play된 음악의 장르 순으로, 각 장르에서 최대 2개까지의 음악 고유번호를 출력하는 문제

문자열을 기준으로 Play횟수를 카운팅 해야하므로 맵을 써야된다.

장르가 중복으로도 주어지므로 각 고유번호 별 Play횟수를 알아야 한다.

즉, 장르별 Play횟수의 합과 음악의 고유번호, 개별 Play횟수를 모두 알아야 하고, Play의 최대를 알아야 하는 문제

 

 

전역 변수

• Song : 음악의 Play횟수와 고유 번호를 저장하기 위한 구조체
• Desc : 음악의 장르와 Play횟수의 총합을 저장하기 위한 구조체
• dic1 : 음악의 장르와 해당 장르의 음악들을 해시맵으로 저장하기 위한 unordered_map 타입 변수
• dic2 : 음악의 장르와 해당 장르의 Play의 횟수의 총합을 저장하기 위한 unordered_map 타입 변수

 

함수

없음

 

 

문제풀이

1. solution함수의 매개변수로 주어진 장르와 플레이 횟수 벡터의 길이만큼 for문을 개행해 준다.
2. 문자열 s에 장르의 이름을 저장해 주고, 정수 n에 플레이 횟수를 저장해 준다.
3. dic1의 s키의 value에 n과 인덱스 i를 묶어 push해준다. 이때 value는 Song타입 우선순위 큐이다.
4. dic2의 s키의 value에 n만큼 수치를 더해준다. 이때 value는 s장르 Play횟수의 총합이다.
5. 장르와 플레이 횟수에 대한 데이터를 모두 해시맵에 넣었다면, Desc타입의 우선순위 큐 pq를 초기화 한다.
6. dic2를 순회하며 각각의 키와 값을 pq에 추가해 준다, 이는 장르이름과 플레이 총 횟수를 내림차순으로 정렬한다.
7. pq가 빌때까지 반복문을 수행하고 pq안에 있는 플레이수가 가장 큰 장르부터 꺼내준다.
8. dic1의 장르를 키로 갖는 Song타입 우선순위 큐를 songs로 가져와준다.
9. 최대 2개의 노래까지 answer에 넣을 수 있으므로, songs의 사이즈와 2중 작은 것을 변수 ML로 초기화 한다.
10. ML번의 반복문을 수행하고 songs에서 Play가 가장 큰 숫자의 고유 번호를 answer에 추가해 준다.
11. 모든 작업을 마친 후 answer를 리턴해 주면 된다.

 

참고 사항

결국에는 장르를 키로 갖는 해시맵 2개를 갖고 푸는 문제이다.

우선순위 큐도 결국 두개를 써주었다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

struct Song{
    int val, idx;
    bool operator<(const Song& other) const {
        return val < other.val;
    }
};

struct Desc{
    string s;
    int sum;
    bool operator<(const Desc& other) const {
        return sum < other.sum;
    }
};

unordered_map<string, priority_queue<Song>> dic1;
unordered_map<string, int> dic2;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    for (int i = 0; i < genres.size(); i++) {
        string s = genres[i];
        int n = plays[i];
        dic1[s].push({n, i});
        dic2[s] += n;
    }
    
    priority_queue<Desc> pq;
    for (auto dic : dic2) {
        pq.push({dic.first, dic.second});
    }
    
    while (!pq.empty()) {
        Desc desc = pq.top(); pq.pop();
        priority_queue<Song> songs = dic1[desc.s];
        
        int ML = min(2, (int)songs.size());
        while (ML--) {
            Song song = songs.top(); songs.pop();
            answer.push_back(song.idx);
        }
    }
    
    return answer;
}