프로그래머스: 베스트 앨범

[문제 링크]

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

---

제약사항이 많은 문제였는데, 양질의 문제는 아니였던거같다.

 

전체적인 알고리즘은 다음과 같다.

입력받은 vector<string>의 원소를 key 값으로 받는 map<string, int> 컨테이너를 만든 다음 key값과 일치하는 재생횟수를 누적시키고,

마찬가지로 vector<string> 배열의 원소를 key 값으로 받는 map<string, vector<pair<int, int>>> 컨테이너를 만든 다음 key값과 일치하는 재생횟수와, 고유 번호를 pair 쌍으로 저장하여 vector 컨테이너에 쌓는다. 

 

이 과정을 통해 각 장르별 총 재생 횟수와 장르별 고유 번호와 재생 횟수를 파악할 수 있게 된다.

 

그다음 많이 재생된 장르 순으로 오름차순 정렬하고, 장르별 재생 횟수가 많은 고유번호 순으로 정렬을 수행한다.

추가로 문제의 요구사항에 맞춰 재생 횟수가 일치하는 경우 고유번호가 작은 것이 앞에 오도록 처리해주자.

 

마지막으로 가장 많이 재생된 장르순으로 그 장르에서 재생 횟수가 많은 고유번호를 2개 뽑아 answer에 담아주면 된다.

---

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

using namespace std;

bool compare(const pair<int, int> left, const pair<int, int> right)
{
	if (left.first == right.first)
		return left.second < right.second;
	else
		return left.first > right.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;
	map<string, int> playsCnt;
	map<string, vector<pair<int, int>>> genresBest;

	for (int i = 0; i < genres.size(); i++)
	{
		playsCnt[genres[i]] += plays[i];
		genresBest[genres[i]].push_back(make_pair(plays[i], i));
	}

	map<string, int>::iterator iter = playsCnt.begin();
	vector<pair<int, string>> sortPlays;

	while (iter != playsCnt.end())
	{
		sortPlays.push_back({ iter->second, iter->first });
		iter++;
	}

	sort(sortPlays.begin(), sortPlays.end(), greater<pair<int, string>>());

	for (int i = 0; i < sortPlays.size(); i++)
	{
		string pick = sortPlays[i].second;
		vector<pair<int, int>> temp = genresBest[pick];

		sort(temp.begin(), temp.end(), compare);

		for (int j = 0; j < temp.size(); j++)
		{
			if (j == 2) break;
			answer.push_back(temp[j].second);
		}

		temp.clear();
	}

	return answer;
}

알고리즘 200일 프로젝트 - 135 day