[알고리즘] 프로그래머스_베스트앨범

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 단순하게 map으로 장르당 최대 재생 수를 기록하고, 장르별로 곡 id, 곡 재생수 pair로 저장해서 정렬 후 계산해주면 될 것 같다.

2. 문제 풀이 과정(삽질)

• map 사용법이 익숙하지 않아서 삽질을 좀 했다.
• 코드를 보면 가독성이 좀 떨어진다.

3. 문제 해결

• 분석과 같이 했다.

3-1. 개인적으로 문제풀다 배운것

• map은 key 기준으로 오름차순 정렬된다. 나중에 이를 써먹자.
• min은 두 인자의 타입이 같아야한다. 아래 코드에서 (int)로 강제 형변환을 하지 않으면 오류가 난다.

4. 코드

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

using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
    if(a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

bool compareOnlySecond(const pair<string, int>& a, const pair<string, int>& b)
{
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> allPlays;
    map<string, vector<pair<int, int>>> songs;
    
    for(int i = 0; i < genres.size(); i++)
    {
        allPlays[genres[i]] += plays[i];
        songs[genres[i]].push_back({plays[i], i});
    }
    
    vector<pair<string, int>> sortedAllPlays(allPlays.begin(), allPlays.end());
    sort(sortedAllPlays.begin(), sortedAllPlays.end(), compareOnlySecond);
    
    for(auto &song : songs)
        sort(song.second.begin(), song.second.end(), compare);
    
    for(auto &play : sortedAllPlays)
    {
        for(int i = 0; i < min(2, (int)songs[play.first].size()); i++)
            answer.push_back(songs[play.first][i].second);
    }
    
    return answer;
}

5. 고수의 코드를 보고 배우기

• 분석할 집중력이 딸린다.

#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;
}