[テストコードC+]ベストアルバム
今日の質問
https://programmers.co.kr/learn/courses/30/lessons/42579#
ベストアルバム
私の答え
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
bool cmp(multiset<pair<int, int>>a , multiset<pair<int, int>> b){
int as = 0;
int bs = 0;
multiset<pair<int, int>>::iterator itera = a.begin();
multiset<pair<int, int>>::iterator iterb = b.begin();
for(;itera != a.end();itera++)
as += (*itera).first;
for(;iterb != b.end();iterb++)
bs += (*iterb).first;
if(as >= bs) return true;
else return false;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
map<string, int> dic;
vector<multiset<pair<int, int>>> num;
int cnt = 0;
for(int i=0;i<plays.size();i++){
if(dic.insert(make_pair(genres[i], cnt)).second == false){ // 이미 있음
num[dic[genres[i]]].insert(make_pair(plays[i], i));
}else{
multiset<pair<int, int>> ms;
ms.insert(make_pair(plays[i], i));
num.push_back(ms);
cnt++;
}
}
sort(num.begin(), num.end(), cmp);
for(int i=0;i<num.size();i++){
multiset<pair<int, int>>::iterator iter = num[i].end();
if(num[i].size()>=2){
pair<int, int> f = (*--iter);
pair<int, int> s = (*--iter);
if(f.first == s.first){
answer.push_back(min(f.second, s.second));
answer.push_back(max(f.second, s.second));
}else{
answer.push_back(f.second);
answer.push_back(s.second);
}
}else{
answer.push_back((*--iter).second);
}
}
return answer;
}
模範解答
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>
using namespace std;
bool compare (pair<int, int> left, pair<int, int> right){
if(left.first > right.first){
return true;
}else if(left.first == right.first){
if(left.second < right.second){
return true;
}
}
return false;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
unordered_map<string, int> summap;
unordered_map<string, vector<pair<int, int>>> genmap;
for (int i = 0; i < genres.size(); i++) {
summap[genres[i]] += plays[i];
genmap[genres[i]].push_back(make_pair(plays[i], i));
}
vector<pair<int, string>> fororder;
for (auto x : summap) {
fororder.push_back(make_pair(x.second, x.first));
}
sort(fororder.begin(), fororder.end());
while (fororder.size() > 0) {
pair<int, string> temp= fororder.back();
fororder.pop_back();
vector<pair<int, int>> a = genmap[temp.second];
sort(a.begin(), a.end(), compare);
int lastn = 2;
if (a.size() < 2) {
lastn = a.size();
}
for (int i = 0; i < lastn; i++) {
answer.push_back(a[i].second);
}
}
return answer;
}
学ぶべきところ
Reference
この問題について([テストコードC+]ベストアルバム), 我々は、より多くの情報をここで見つけました https://velog.io/@huijae0817/코딩테스트C-베스트앨범テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol