베스트앨범

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

얼핏 볼때 쉬어보이는데 못풀었다.

1.맵채우기
map<string, int> genre_cnt;//장르별 재생 횟수
genre_cnt[genres[i]] += plays[i];

2.맵 응용
map < string, vector<pair<int, int>>> genre_playlist;
genre_playlist[genres[i]].push_back(make_pair(plays[i], i));

3.벡터복사
genre_v.assign(genre_cnt.begin(), genre_cnt.end());

내가 평소에 별로 안다루는 방식인데,
이문제 힙 유형으로 여러번 더 풀어볼 가치있음.

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

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

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


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

	vector<int> answer;


	map<string, int> genre_cnt;//장르별 재생 횟수
	map < string, vector<pair<int, int>>> genre_playlist;//장르별 노래의 재생횟수 및 고유번호
	vector<pair<string, int>> genre_v;//장르별 노래갯수

		for (int i = 0; i < genres.size(); i++)
		{
			genre_cnt[genres[i]] += plays[i];

			genre_playlist[genres[i]].push_back(make_pair(plays[i], i));
		}


		map < string, vector<pair<int, int>>>::iterator itr;

		for (itr = genre_playlist.begin(); itr != genre_playlist.end(); itr++)//재생횟수를 이용한 내림차순 정렬
		{
			sort(itr->second.begin(), itr->second.end(), cmp);
		}

		genre_v.assign(genre_cnt.begin(), genre_cnt.end());
		sort(genre_v.begin(), genre_v.end(), cmp_song_cnt);

		for (int i = 0; i < genre_v.size(); i++)
		{
			string genre_name = genre_v[i].first;


			for (int j = 0; (j < genre_playlist[genre_name].size() && j < 2); j++)
			{
				answer.push_back(genre_playlist[genre_name][j].second);
			}
		}



		return answer;
}