Programmers / hash / 베스트앨범

< 문제링크 >

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

< 풀이 >

1. 장르별로 누적 재생수를 저장 -> map

2. 누적 재생수에 대해서 정렬이 필요하므로 reverseMap을 만들어 (누적재생수, 장르)로 복사해서 저장

-> 이 때, 오름차순 정렬이 되므로 역순으로 탐색해야 됨

3. 각 장르에 해당하는 곡들을 추출하여 저장 -> vector에 pair(곡번호, 재생수)

4. vector를 재생수 기준으로 내림차순 정렬 (같으면 곡번호가 낮은 것 우선) -> sort() 함수사용

5. 해당 vector에서 상위 2개 항목이 원하는 답이므로 answer에 누적

-> 이 때, 노래가 하나인 경우도 있으므로 예외 처리!

< 코드 > 

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

using namespace std;

bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if (p1.second > p2.second) return true;
    else if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> genrePlay;		// 장르별 누적 재생수
    map<int, string> reverseMap;	// genrePlay을 reverse하여 오름차순 정렬

    // 장르별 누적 재생수 초기화
    for (string name : genres) {
        genrePlay[name] = 0;
    }
    // 누적 재생수 구성
    for (int i = 0; i < plays.size(); i++) {
        genrePlay[genres[i]] += plays[i];
    }
    // reverseMap 만들기
    for (auto tmp = genrePlay.begin(); tmp != genrePlay.end(); tmp++) {
        reverseMap.insert({ tmp->second, tmp->first });
    }
    // reverseMap을 거꾸로 탐색하면서 각 노래를 vector에 추가
    for (auto tmp = reverseMap.rbegin(); tmp != reverseMap.rend(); tmp++) {
        // 각 노래를 저장할 vector 선언
        vector<pair<int, int>> songs;
        for (int i = 0; i < plays.size(); i++) {
            // 현재 조사하고 있는 장르면 vector에 추가
            if (tmp->second == genres[i]) {
                songs.push_back({ i, plays[i] });
            }
        }
        sort(songs.begin(), songs.end(), cmp);
        auto high = songs.begin();
        answer.push_back(high->first);
        high++;
        if (high != songs.end()) {
            answer.push_back(high->first);
        }
    }
    return answer;
}

int main(void)
{
    vector<string> genres = { "classic", "pop", "classic", "classic", "pop" };
    vector<int> plays = { 500, 600, 150, 800, 2500 };
    vector<int> answer = solution(genres, plays);
    for (auto i : answer) {
        cout << i << " ";
    }
    return 0;
}