[ハッシュ]ベストアルバム

|問題説明|

_ genres[i] : 고유번호가 i인 노래의 장르
_ plays[i] : 고유번호가 i인 노래가 재생된 횟수
_ genres의 길이 = plays의 길이, 1 이상 10,000 이하
_ 장르 종류 : 100개 미만
_ 장르에 속한 곡이 하나라면, 하나의 곡만 선택
_ 모든 장르는 재생된 횟수가 다르다.

||トラブルシューティング|

- g : genres 속에 속한 장르의 종류
- tmp1 : 해당 장르의 총 plays 개수, 해당 장르의 g위치
- tmp2 : 해당 장르의 첫 번째 수록곡, 두 번째 수록곡
- m : 장르별 plays 모음

- m에 각 genres에 해당하는 plays를 추가하고, genres에 등장하는 장르들을 g에 모아둠
- 각 장르들의 첫 번째, 두 번째 수록곡을 정하는 과정
	(첫 번재 과정에서 해당 장르의 총 합산을 구하고 for문으로 제일 큰 값 저장. 
    	두 번째 과정 전에 해당 장르의 곡이 하나인지 아닌지 판단하여 따로 구함. 
    	각 값들을 tmp1,tmp2에 저장)
- tmp1을 정렬한 후에 tmp1의 순서에 따라 tmp2의 값들을 answer에 추가

|コード|

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    vector<string> g;
    vector<pair<int, int>> tmp1, tmp2;
    map<string, vector<int>> m;
    for(int i = 0; i < genres.size(); i++) {
        if(m[genres[i]].empty()) g.push_back(genres[i]);
        m[genres[i]].push_back(i);
    }
    for(int i = 0; i < g.size(); i++) {
        int max1 = 0, max2 = 0, in1, in2, sum = 0;
        for(int j = 0; j < m[g[i]].size(); j++) {
            sum += plays[m[g[i]][j]];
            if(plays[m[g[i]][j]] > max1) {
                max1 = plays[m[g[i]][j]];
                in1 = m[g[i]][j];
            }
        }
        if(m[g[i]].size() != 1) {
            for(int j = 0; j < m[g[i]].size(); j++) {
                if(plays[m[g[i]][j]] > max2 && plays[m[g[i]][j]] < max1) {
                    max2 = plays[m[g[i]][j]];
                    in2 = m[g[i]][j];
                }
            }
        }
        else in2 = -1;
        tmp1.push_back({sum, i});
        tmp2.push_back({in1, in2});
    }
    sort(tmp1.begin(), tmp1.end(), compare);
    for(auto i : tmp1) {
        answer.push_back(tmp2[i.second].first);
        if(tmp2[i.second].second != -1) answer.push_back(tmp2[i.second].second);
    }
    return answer;
}

- 조건문 추가 : 첫 번째, 두 번째 plays의 횟수가 같을 경우를 고려하여 plays[m[g[i]][j]] <= max1 수정 및 m[g[i]][j] != in1 추가

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    vector<string> g;
    vector<pair<int, int>> tmp1, tmp2;
    map<string, vector<int>> m;
    for(int i = 0; i < genres.size(); i++) {
        if(m[genres[i]].empty()) g.push_back(genres[i]);
        m[genres[i]].push_back(i);
    }
    for(int i = 0; i < g.size(); i++) {
        int max1 = 0, max2 = 0, in1, in2, sum = 0;
        for(int j = 0; j < m[g[i]].size(); j++) {
            sum += plays[m[g[i]][j]];
            if(plays[m[g[i]][j]] > max1) {
                max1 = plays[m[g[i]][j]];
                in1 = m[g[i]][j];
            }
        }
        if(m[g[i]].size() != 1) {
            for(int j = 0; j < m[g[i]].size(); j++) {
                if(plays[m[g[i]][j]] > max2 && plays[m[g[i]][j]] <= max1 && m[g[i]][j] != in1) {
                    max2 = plays[m[g[i]][j]];
                    in2 = m[g[i]][j];
                }
            }
        }
        else in2 = -1;
        tmp1.push_back({sum, i});
        tmp2.push_back({in1, in2});
    }
    sort(tmp1.begin(), tmp1.end(), compare);
    for(auto i : tmp1) {
        answer.push_back(tmp2[i.second].first);
        if(tmp2[i.second].second != -1) answer.push_back(tmp2[i.second].second);
    }
    return answer;
}