[프로그래머스 문제풀이] 5. 베스트앨범

해시 테이블을 이용하는 unordered_map 사용

unordered_map에 저장되는 형식은
[key : 장르, value : (고유번호, 재생 수)]이다.

unordered_map<string, vector<pair<int, int>>> hash_map;

---

여기서 정렬을 하는데 요구 조건이 좀 까다롭다.
value값을 정렬하는데 고유번호가 같다면 재생 수 별로 정렬하고
고유번호가 다르다면 고유번호로 정렬한다.
코드로 표현하자면 다음과 같다.

for (auto& keyvalue : hash_map)
  sort(keyvalue.second.begin(), keyvalue.second.end(), [](pair<int, int> a, pair<int, int> b) {
              if (a.second == b.second)
                  return a.first < b.first;
              else
                  return a.second > b.second;
              });

---

장르가 더 많이 재생된 것이 먼저 수록되어야 되기 때문에 자료구조를 하나 더 만들어서 정렬한다.

map<int, string, greater> hash_map2;

형식은 [key : 장르 재생 수, value : 장르 이름]이다.
greater<>를 넣어서 재생 수가 많은 것을 앞 쪽으로 오도록 정렬한다.
unordered_map을 사용하면 정렬이 보장이 안되므로 map을 사용했다.

---

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

using namespace std;

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

    unordered_map<string, vector<pair<int, int>>> hash_map;
	map<int, string, greater<int>> hash_map2;

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

	for (auto& keyvalue : hash_map)
	{
		sort(keyvalue.second.begin(), keyvalue.second.end(), [](pair<int, int> a, pair<int, int> b) {
			if (a.second == b.second)
				return a.first < b.first;
			else
				return a.second > b.second;
			});

		int totalplay = 0;

		for (auto p : keyvalue.second)
		{
			totalplay += p.second;
		}

		hash_map2[totalplay] = keyvalue.first;
	}

	for (auto keyvalue : hash_map2)
	{
		answer.push_back(hash_map[keyvalue.second][0].first);
		if (hash_map[keyvalue.second].size() > 1)
			answer.push_back(hash_map[keyvalue.second][1].first);
	}

    return answer;
}

int main()
{
    for(auto d : solution({ "classic", "pop", "classic", "classic", "pop", "head"}, {500, 600, 150, 800, 2500, 100}))
		cout << d << '\n';
}

실행결과

4
1
3
0

베스트 앨범 문제 링크