프로그래머스: 베스트앨범 (C++)

문제 링크는 아래와 같다.

https://www.welcomekakao.com/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범 | 프로그래머스

 

 

두 개의 map을 이용했으며, 하나의 map에는 장르별 전체 재생 횟수를 저장했다.

 

또 다른 map에는 key에 장르를, value에 pair 벡터를 저장했다. pair에는 노래의 재생 횟수와 인덱스가 들어가도록 했다.

 

 

map을 구하고 나면, 정렬을 용이하게 하기 위해서 vector를 이용한다.

 

문제의 조건에 따라 정렬 조건을 맞춰주고 답을 구해주면 된다.

 

 

#include <string>
#include <vector>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;

struct Info {
	string str;
	int cnt;
};

bool cmp(pii a, pii b) {
	if (a.first != b.first) 
		return a.first > b.first; //재생 횟수 따라 정렬
	else
		return a.second < b.second; //재생 횟수가 같으면 노래 번호 오름차순으로 정렬
}

bool cmp2(Info a, Info b) {
	return a.cnt > b.cnt; //총 재생 횟수 정렬
}

map<string, vector<pii> > mp; //장르별 노래 재생 횟수
map<string, int> cntMap; //총 재생 횟수

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

	int songNum = 0;
	for (int i = 0; i < genres.size(); i++) {
		if (mp.find(genres[i]) == mp.end()) {
			vector<pii> tmp;
			tmp.push_back({ plays[i], i }); //i번째 곡이 저만큼 플레이 됨
			mp.insert({ genres[i], tmp });
			cntMap.insert({ genres[i], plays[i] });
		}
		else {
			mp[genres[i]].push_back({ plays[i], i });
			cntMap[genres[i]] += plays[i]; //토탈 추가
		}
	}


	for (auto itr = mp.begin(); itr != mp.end(); itr++) 
		sort(itr->second.begin(), itr->second.end(), cmp); //노래 재생 횟수 내림차순 정렬
	
	

	vector<Info> sortVec; //정렬하기 위해 옮겨담기. <장르, 총재생수>

	for (auto itr = cntMap.begin(); itr != cntMap.end(); itr++) 
		sortVec.push_back({ itr->first, itr->second }); //정렬하기 편하게 벡터에 복사
	
	sort(sortVec.begin(), sortVec.end(), cmp2); //정렬

	for (int i = 0; i < sortVec.size(); i++) {
		string gen = sortVec[i].str;
		answer.push_back(mp.find(gen)->second[0].second);
		if (mp.find(gen)->second.size() > 1) //하나 이상인 경우에만 2번째까지
			answer.push_back(mp.find(gen)->second[1].second);
	}
	return answer;
}