[코딩테스트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;
}

배울 점

• 자료 구조를 어떻게 삼을가에 대한 고민을 오래했다. map으로 두어야할것과 저장과 정렬해야할 것을 따로 잡았다. map의 value는 인덱스를저장하고 해당 인덱스를 가진 vector내부의 multiset에 플레이횟수와 음악고유번호를 저장했다.
• 모두 저장 후 Vector를 장르 플레이횟수에 대해 sort하고, multiset에 의해 그 내부는 정렬되었으니, 큰 수의 인덱스를 출력한다.
• 이 문제는 로직이 어려운 문제는 아니지만 구성을 어떻게 하는가가 중요한 문제같다. 구현능력평가