해시 - 베스트앨범

C++

해시 - 베스트앨범

문제

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

문제 출처

접근 방법

각 곡의 모든 정보를 하나의 map에 넣는다. 각 장르별 정렬은 이후 sort를 통해 구현 할 것이므로 정렬 없이 저장만 하는 unordered_map을 사용하였다.
처음 장르를 발견하면 재생 횟수를 사각 장르가 존재 할 시에,

구현

코드

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

using namespace std;

bool comp(pair<string, map<int, int>> a, pair<string, map<int, int>> b) {
    int aTotal = 0;
    int bTotal = 0;
    map<int, int> aa = a.second;
    map<int, int> bb = b.second;
    map<int, int>::iterator aiter;
    for (aiter = aa.begin(); aiter != aa.end(); aiter++) {
        aTotal += aiter->first;
    }
    map<int, int>::iterator biter;
    for (biter = bb.begin(); biter != bb.end(); biter++) {
        bTotal += biter->first;
    }

    return aTotal > bTotal;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, map<int, int>> playorder;
    for (int i = 0; i < genres.size(); i++) {
        if (playorder.count(genres[i]) == 0) {
            map<int, int> temp;
            temp.insert(make_pair(plays[i], i));
            playorder[genres[i]] = temp;
        }
        else {
            map<int, int> temp = playorder[genres[i]];
            if (temp.count(plays[i]) != 0) {
                plays[i]--;
            }
            temp.insert(make_pair(plays[i], i));
            playorder[genres[i]] = temp;
        }
    }

    vector<pair<string, map<int, int>>> vec(playorder.begin(), playorder.end());
    sort(vec.begin(), vec.end(), comp);

    for (int i = 0; i < vec.size(); i++) {
        map<int, int> temp = vec.at(i).second;
        if (temp.size() == 1) {
            map<int, int>::iterator iter;
            for (iter = temp.begin(); iter != temp.end(); iter++)
                answer.push_back(iter->second);
        }
        else {
            map<int, int>::reverse_iterator riter(temp.rbegin());
            int idx = 0;
            for (; riter != temp.rend(); ++riter) {
                if (idx == 2)
                    break;
                answer.push_back(riter->second);
                idx++;
            }
        }
    }
    return answer;
}

후기 및 개선할 점