프로그래머스 Level 3 베스트앨범

베스트앨범 (프로그래머스 Level 3)

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

해결 아이디어 자체는 간단하지만,
자료구조를 어떻게 써야 하는지, C++의 stl 에 대하여 능숙한지 물어보는 문제였다

고민했던 점은

1. 장르별 합을 통해, 먼저 넣을 장르를 고르기
   
2. 각 장르별로 각각의 play 횟수에 따라 가능한 2개씩 고르기
   

처음에는 map만 필요하다 생각하였으나,
map으로 합을 별도로 저장하더라도, 정렬의 필요성을 느꼈다
(정확히는 map에 정렬하여 넣더라도, 내부 데이터를 수정 이후, 재정렬이 필요)
추가적으로 조건에 맞는 best 2개를 골라야 하기에 우선순위 큐를 map의 second로 별도로 저장하였다

Code

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

using namespace std;

typedef pair<int, int> pii;

struct Compare
{
	bool operator()(const pii& a, const pii& 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;

	// 1. vector에 pair로 string과 장르별 sum을 담기
	// 2. map에는 string과 우선순위 큐를 담기
	// 3. vector 를 sum 기준으로 정렬
	// 4. vector의 반복문을 돌며 map에 저장해둔 우선순위 큐에서 가능한 2개씩 빼기
	// 5. 뺀 녀석들의 index를 answer에 담아주기

	map<string, int> m1;
	map <string, priority_queue<pii, vector<pii>, Compare>> m2;

	int gS = static_cast<int>(genres.size());

	for (int i = 0; i < gS; i++)
	{
		if (m2.find(genres[i]) == m2.end())
		{
			m1[genres[i]] = 0;
			m2[genres[i]] = priority_queue<pii, vector<pii>, Compare>();
		}

		m1[genres[i]] += plays[i];
		m2[genres[i]].push(make_pair(plays[i], i));
	}

	vector<pair<string, int>> vec(m1.begin(), m1.end());
	sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {return a.second > b.second; });

	for (int i = 0; i < vec.size(); i++)
	{
		int tempSize = m2[vec[i].first].size();
		for (int j = 0; j < tempSize; j++)
		{
			if (j >= 2)
				break;

			int ind = m2[vec[i].first].top().second;
			m2[vec[i].first].pop();

			answer.push_back(ind);
		}
	}

	return answer;
}

int main()
{
	vector<string> gen = { "classic", "pop", "classic", "classic", "pop" };
	vector<int> pla = { 500, 600, 150, 800, 2500 };

	solution(gen, pla);

	return 0;
}

해결 아이디어

1. 가장 재생 횟수가 많은 수의 ‘장르’ 별로 정렬이 필요하여 map 과 벡터를 이용
   
2. 추가적으로 각 장르 별, play 수가 가장 많은 것을 얻어내기 위하여 map 과 우선순위 큐를 이용
   
3. vector를 통하여 ‘장르’의 총 재생 수가 많은 순서대로 선택,
   map과 우선순위 큐를 통해, 해당 장르에서 재생순위가 높은 인덱스를 우선적으로 2개 선택