[Programmers]#Level3_베스트 앨범, map, priority_queue, erase, sort, predicate 함수

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. map 컨테이너

https://webddevys.tistory.com/104

[Basic C++] #38_map, 연관 컨테이너

C++ 표준 라이브러리에서 제공하는 map 컨테이너는 지정된 형식의 키와 값을 한 쌍으로 레드-블랙 트리(균형 이진트리) 자료구조에 저장하는 연관 컨테이너입니다. map 컨테이너는 키의 중복을 혀용 하지 않고 키를 기준으로 내부적으로 정렬된 상태를 유지하는 특징이 있습니다.

 

2. unordered_map 컨테이너

[Basic C++] #72_unordered_map

C++ 표준 라이브러리에서 제공하는 um 컨테이너는 키와 값을 한 쌍으로 해시 자료구조에 저장하는 연관 컨테이너입니다. um 컨테이너는 키의 중복을 허용하지 않고 내부적으로 정렬된 상태를 유지하지 않는 것이 특징입니다. 

 

3. priority_queue 컨테이너

[Basic C++] #69_priority_queue

C++ 표준 라이브러리에서 제공하는 priority_queue 컨테이너는 각 항목에 우선순위를 할당하고, 가장 우선순위가 높은 항목부터 먼저 제거되는 힙 자료구조를 가집니다. 따라서, pq 컨테이너는 항목의 삽입 순서와 무관하게 우선순위를 기준으로 내부적으로 반 정렬 상태를 유지합니다. 기본적으로, '최대 힙(우선순위가 높은 항목이 먼저 제거되는)'으로 설정되며, greater <type_name>() 혹은 함수 객체를 통해 정렬 기준을 '최소 힙'으로 변경할 수 있습니다.

 

3. 여러 가지의 컨테이너 활용과 sort 알고리즘에 predciate 활용하기!

1. 먼저, map 컨테이너를 통해 각 장르 별 총 재생 횟수를 세어줍니다. 더불어, um(unordered_map) 컨테이너를 통해 각 장르 별 고유 번호들을 저장합니다.
2. 첫 번째 조건(장르 우선순위: 속한 노래가 많이 재생된 장르 먼저 수록) 충족을 위해 map 컨테이너를 차례대로 순회하며, 우선순위 큐에 pair< 총 재생 횟수, 장르 > 형식으로 삽입해 줍니다.
3. 두 번째 조건과 세 번째 조건( 장르 내 재생 횟수가 가장 많은 곡, 재생 횟수가 같다면 인덱스가 더 낮은 곡) 충족을 위해 다중 조건 비교를 수행하는 predicate 함수를 람다 함수로 정의합니다. 먼저, pair < 재생 횟수, 곡의 고유 번호 >에서, 총 재생 횟수가 더 많은 곡을 앞으로 위치시키며, 재생 횟수가 같다면 고유 번호가 더 적은 곡을 앞으로 위치시킵니다.
4. 그리고. 이렇게 정렬된 각 장르별 곡들의 고유 번호들을 가장 앞에 두 곡을 제외하고 erase 알고리즘을 활용하여 모두 제거해 줍니다.
5. 마지막으로, 우선순위 큐를 차례대로 순회하며, 각 장르별 두 개의 고유 번호들을 정답 목록에 삽입해 주고, 결과 목록을 반환합니다.

 

---

 

#3. 코드

/*
    @문제: 장를 별 가장 많이 재생된 두 곡을 찾아 목록을 구성하여 반환.
    @설명
        조건1: 앨범 내 최대 플레이 횟수가 가장 큰 장르를 먼저 수록
        -> map+pq 활용: map 컨테이너 활용하여 각 장르 별 총 재생 횟수를 카운트 하고, 이를 priority_queue에 '재생 횟수'기준 최대 힙으로 구성

        조건2: 장르 내 플레이 횟수가 가장 큰 곡을 먼저 수록
        조건3: 장르 내 플레이 횟수가 같을 경우 고유 번호가 더 적은 곡을 먼저 수록
        -> sort&predicate 활용: 두 가지 조건을 정의하는 Predicate를 활용해, 각 장르별 최대 재생 횟수를 갖는 곡들을 앞으로 정렬
        -> erase 활용: 각 장르별 최대 재생 횟수 두 곡을 제외한 나머지 곡들을 제거
        
        결과: pq를 순회하며, 가장 재생 횟수가 많은 장르 부터 두 곡을 뽑아서 베스트 앨범 목록에 한 곡 혹은 두 곡 삽입
*/

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

using namespace std;

// 장르 별 총 재생 횟수
map<string, int> m;
// pair < 장르 이름, vector < pair < 재생 횟수, 고유 번호 > >
unordered_map<string, vector<pair<int,int>>> um;
// 우선순위 큐
priority_queue<pair<int,string>, vector<pair<int,string>>> pq;
vector<int> ans;

vector<int> solution(vector<string> genres, vector<int> plays) {

    // um 구성 + pq 구성
    for(int i=0; i<(int)genres.size(); ++i)
    {
        string genre = genres[i];
        int play = plays[i];

        m[genre] += play;
        um[genre].push_back({play, i});
    }

    // 조건1: 장르 우선순위: 속한 노래가 많이 재생된 장르 먼저 수록
    for(auto it = begin(m); it!=end(m); ++it)
    {
        pq.push({(*it).second, (*it).first});
    }

    // 조건2+조건3: 장르 내 재생 횟수가 가장 많은 곡, 재생 횟수가 같다면 인덱스가 더 낮은 곡.
    for(auto it = begin(um); it!=end(um); ++it)
    {
        // 곡이 하나면, 정렬 안함
        if((*it).second.size() > 1)
        {
            sort(begin((*it).second), end((*it).second), [](const pair<int,int>& a, const pair<int,int>& b)
            {
                if(a.first == b.first)
                    return a.second < b.second;
                else
                    return a.first > b.first;
            });
            // 가장 앞에 두 곡을 제외하고, 모두 지워
            (*it).second.erase(begin((*it).second)+2, end((*it).second));
        }
    }

    while(!pq.empty())
    {
        string genre = pq.top().second;
        pq.pop();
        // 정답 목록에 한 곡 혹은 두 곡 삽입
        if(um[genre].size() < 2)
        {
            ans.push_back(um[genre][0].second);
        }
        else
        {
            ans.push_back(um[genre][0].second);
            ans.push_back(um[genre][1].second);
        }
    }

    return ans;
}

 

---