[해시] 베스트앨범

|| 문제설명 ||

1. 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다.
2. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같다.
   • 속한 노래가 많이 재생된 장르를 먼저 수록한다.
   • 장르 내에서 많이 재생된 노래를 먼저 수록한다.
   • 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
3. 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하라.

• genres : 노래의 장르를 나타내는 문자열 배열
• plays : 노래별 재생횟수를 나타내는 정수 배열

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

---

|| 문제해결방법 ||

1) 변수 소개

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

2) 알고리즘

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

---

|| 코드 ||

[2020.09.22] 실패

#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의 횟수가 같을 경우?

---

[2020.09.22] 성공

- 조건문 추가 : 첫 번째, 두 번째 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;
}