[프로그래머스 Level 3] 베스트앨범(C++)

코딩테스트 연습 - 베스트앨범 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

구현 문제라고 보면 된다. priority_queue를 이용해서 재생횟수에 대해 내림차순, 고유 번호에 대해 오름차순으로 정렬해주면 된다.

 

 

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

struct element {
	int c;
	int n;
};

struct compare {
	bool operator() (element a, element b) {
		if (a.c == b.c) {
			return a.n > b.n;
		}
		else {
			return a.c < b.c;
		}
	}
};

priority_queue<element, vector<element>, compare> pq[101];
map<string, int> m;
pair<int, int> total[101];

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;
	int c = 1;
	for (int i = 0; i < genres.size(); i++) {
		if (m[genres[i]] == 0) {
			m[genres[i]] = c++;
		}
		element e;
		e.c = plays[i];
		e.n = i;
		total[m[genres[i]]].first += plays[i];
		total[m[genres[i]]].second = m[genres[i]];
		pq[m[genres[i]]].emplace(e);
	}
	sort(total + 1, total + c, greater<>());
	for (int i = 1; i < c; i++) {
		int n = total[i].second;
		int co = 0;
		while (!pq[n].empty()&&co<2) {
			answer.push_back(pq[n].top().n);
			co++;
			pq[n].pop();
		}
	}
	return answer;
}