[프로그래머스 lv3] 베스트앨범 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

해시를 이용하여 장르별 정보를 처리하는 문제이다.

 

1) map<string, int> nplay: 장르별 재생 횟수를 저장한다.

2) map<string, vector<ii>> minfo: 장르별로 곡의 (재생수, 번호) 배열을 저장한다.

3) minfo[장르]을 내림차순으로 정렬한다. 이때, 같은 재생 수를 가진 곡에 대해서는 곡 번호가 작은 녀석이 앞에 오도록 정렬한다.

4) nplay를 배열(vnplay)로 만들고 재생수 기준 내림차순으로 정렬한다.

 

이후, vnplay에 저장된 순으로 장르를 순회하면서 minfo[장르]의 가장 앞쪽 두 곡 번호를 벡터에 저장한다.

곡 번호가 기록된 벡터를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using is = pair<int, string>;

#define X first
#define Y second

bool cmp(ii a, ii b) {
    if (a.X > b.X) return true;
    if (a.X < b.X) return false;
    if (a.Y < b.Y) return true;
    return false;
}

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

    map<string, vector<ii>> minfo;
    map<string, int> nplay;

    int sz = genres.size();
    for (int i=0; i<sz; i++) {
        nplay[genres[i]] += plays[i];
        minfo[genres[i]].push_back({plays[i], i});
    }

    for (auto it=minfo.begin(); it!=minfo.end(); it++) {
        sort((*it).Y.begin(), (*it).Y.end(), cmp);
    }

    vector<is> vnplay;
    for (auto [g, n] : nplay) vnplay.push_back({n, g});
    sort(vnplay.begin(), vnplay.end(), greater<>());

    vector<int> vans;
    for (auto [n, g] : vnplay) {
        for (int i=0; i<2 && i<minfo[g].size(); i++)
            vans.push_back(minfo[g][i].Y);
    }
    return vans;
}