[프로그래머스] 레벨3 베스트앨범

programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

맵 응용 문제다.

1. 장르별 조회수를 조회해서 조회수에 따라 장르를 내림차순 정렬

2. 장르별 노래 수집

2-1. 노래 고유번호와 play수를 수집

2-2. play수를 기준으로 내림차순, 노래 고유번호를 기준으로 오름차순

 

처음에 전체 배열을 조회하며 map을 사용해서 map[gen] += play를 해준다.

동시에 value가 vector인 map을 선언해서 장르별로 노래를 정리한다.

value에 벡터 선언하는 법 기억해두자.

map<string, vector<pair<int, int>> m;
m["hello"].push_back(make_pair(0,0));

 

맵을 play수대로 정렬해야 하는데 벡터에 맵을 복사한 후에 벡터를 sort해준다.

vector<pair<int, int>> v(m.begin(), m.end());
// map<int, int> m

sort(v.begin(), v.end(), cmp);

 

장르별 조회수를 기준으로 장르에 해당하는 노래를 찾아서 소팅하여 상위 2개만 추출한다.

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;

struct s{
    int play, num;
};
map<string, int> m;
unordered_map<string, vector<s>>um;

bool cmp(const pair<string, int> &t1, pair<string, int> &t2){
    return t1.second > t2.second;
}

bool cmp2(const s& t1, const s&t2){
    if(t1.play == t2.play){
        return t1.num < t2.num;
    }
    return t1.play> t2.play;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int len = genres.size();
    for(int i=0; i<len; i++){
        m[genres[i]]+= plays[i];
        um[genres[i]].push_back({plays[i], i});
    }
    
    vector<pair<string, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<v.size(); i++){
        string gen = v[i].first;
        vector<s> tmp = um[gen];
        
        if(tmp.size() == 1){
            answer.push_back(tmp[0].num);
        }else {
            sort(tmp.begin(), tmp.end(), cmp2);
            answer.push_back(tmp[0].num);
            answer.push_back(tmp[1].num);
        }
    }
    return answer;
}