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

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

using namespace std;

map<string,int> ma;

bool cmp(pair<string,int> a, pair<string,int> b) {
    return a.second > b.second;
}

bool compare(pair<int,int> a, pair<int,int> b) {
    if(a.first == b.first) {
        return a.second < b.second;
    }
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    for(int i=0; i<genres.size(); i++) {
        ma[genres[i]] = ma[genres[i]] + plays[i];
    }
    
    vector<pair<string,int>> vec(ma.begin(),ma.end());
    sort(vec.begin(),vec.end(),cmp);
    
    for(int i=0; i<vec.size(); i++) {
        //플레이 수, 인덱스
        vector<pair<int,int>> idx;
        for(int j=0; j<genres.size(); j++) {
            if(genres[j] == vec[i].first) {
                idx.push_back({plays[j],j});
            }
        }
        sort(idx.begin(),idx.end(),compare);
        if(idx.size() == 1) {
            answer.push_back(idx[0].second);
        }
        else if(idx.size() >= 2){
            for(int j=0; j<2; j++) {
                answer.push_back(idx[j].second);
            }
        }
    }
    
    
    return answer;
}

 

 

** 프로그램 흐름도

1. 장르에 따른 플레이 횟수를 해시를 이용해 저장, 해시값을 벡터에 삽입한뒤 벡터를 내림차순으로 정렬

2. genres 배열을 탐색하며 현재 벡터의 장르와 같은 장르라면 플레이 수, 인덱스를 pair를 이용해 저장

3. 저장된 벡터(pair) 값을 플레이 수 기준 내림차순 인덱스 기준 오름차순으로 정렬

4. 2개 이하까지 값 삽입

 

 

 

프로그래머스 고득점kit 에 어떤 알고리즘 기법을 써야하는지 다 나와서 level3 인데 풀이 난이도가 상당히 쉽다. 가려져있으면 참 좋았을텐데