[알고리즘문제] 프로그래머스 - 베스트 앨범

문제가 수학적인 지식을 필요로 하는 문제는 아니지만 기본적인 문제 분석, 얼마나 자료구조를 잘 사용하는지를 물어보는 문제인 것 같습니다.

 

전체적인 아이디어는 [장르 : 장르별 총 재생횟수], [장르 : 장르별 음악들의 정보(고유번호, 재생횟수)] 두개의 자료구조를 사용하였습니다. 

2개의 자료구조로 2중 포문을 사용하였고, 장르가 같으면 해당 장르별 음악들의 정보에서 값을 answer에 넣어주는 방법을 사용하였습니다.

 

전체적인 위의 방식으로 문제를 풀었고 이 문제를 풀 때 고민했던 부분이 몇가지 있는데, 

 

1. 각 장르별로 총 재생횟수를 체크하고 어떻게 총 재생횟수가 큰 값부터 정렬할까 ?

 첫번째는 먼저 [ 장르 : 총 재생횟수] 를 map으로 체크하였습니다. map을 기본적으로 key를 기준으로 오름차순 정렬이 되는데, 저희가 필요한 건 value로 내림차순 이기 때문에 map -> vector<고유번호, 재생횟수>로 만들어 주고 재생횟수를 기준으로 내림차순 하였습니다(comp1).

 

2. 각 장르별로 어떻게 고유번호, 재생횟수를 관리할까 ?

 두번째도 역시 처음에는 [장르 : vecotr<pair<고유번호 : 재생횟수>>] 구조로 map을 사용하였습니다. 장르에 해당하는 여러개의 음악들 정보(고유번호, 재생횟수)를 value에 넣어줍니다.

 문제에서 "1. 음악들을 재생횟수가 높은 순부터 넣어준다, 2. 재생횟수가 같으면 고유번호가 낮은 것을 먼저 넣어준다" 라는 조건이 있습니다. 이것또한 정렬해야 하기 때문에 map -> vecotr구조로 만들었고 조건대로 정렬해 주었습니다(comp2).

 

그리고 문제에서 최대 2개까지 answer에 넣을 수 있고 장르에 속한 곡이 하나라면 1개만 넣으라고 했습니다.

이 부분은 for문에서 3항 연산자를 사용하여 처리하였습니다.

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

using namespace std;

int comp1(pair<string, int> p1,pair<string, int> p2){ // 총 재생수가 높은 순으로
    return p1.second > p2.second;
}

int comp2(pair<int, int> p1, pair<int, int> p2){ // 각 장르 내에서 재생수가 높은 순으로, 재생수가 같으면 고유번호가 낮은 순으로
    if(p1.second == p2.second){
        return p1.first < p2.first;
    }
    return p1.second > p2.second;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    
    vector<int> answer;
    
    map<string, int> m1;                        // 장르 : 총 재생횟수 
    map<string, vector<pair<int, int>>> m2;     // 장르 : vecotr<고유번호 : 재생횟수>
    

    for(int i=0;i<genres.size();i++){ 
        
        string key = genres[i];
        int value = plays[i];
        
        m1[key]+=plays[i];                         // 총 재생횟수 계산
        
        if(m2.find(key) == m2.end()){              // 장르별 음악들의 고유번호, 재생횟수 계산
            vector<pair<int, int>> v;
            v.push_back(make_pair(i,plays[i]));
            m2[key] = v;
        }else{
            vector<pair<int, int>> v = m2[key];
            v.push_back(make_pair(i,plays[i]));
            m2[key] = v;
        }
    }
    

    vector<pair<string,int>> count(m1.begin(),m1.end());         // map(장르 : 총 재생횟수) -> vector 변환                          
    vector<pair<string, vector<pair<int, int>>>> info(m2.begin(),m2.end());   // map(장르 : vecotr<고유번호, 재생횟수>) -> vector 변환                
    
    sort(count.begin(),count.end(),comp1); // 총 재생수가 높은 순으로 정렬
    
    for(int a=0;a<count.size();a++){ // 이미 총 재생횟수가 높은 순으로 정렬되어 있음
            for(int b=0;b<info.size();b++){
                if(count[a].first == info[b].first){ // 각 장르 내에서 재생수가 높은 순으로, 재생수가 같으면 고유번호가 낮은 순으로
                    
                    vector<pair<int, int>> v = info[b].second;
                    sort(v.begin(),v.end(),comp2); // 각 장르 내에서 재생수를 기준으로 내림차순, 재생수가 같으면 고유번호가 낮은 순으로 정렬
                    
                    for(int i=0;i<(v.size() == 1 ? 1 : 2);i++){ // 최대 2개까지 넣을 수 있고, 곡이 1개면 하나만 넣는다
                        answer.push_back(v[i].first);
                    }
                }
            }
    }
    
    return answer;
}