[프로그래머스] 베스트앨범(C++)

1. C++ Unordered_map vs map

unordered_map

• map보다 더 빠른 탐색을 하기 위한 자료구조 입니다.
• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)입니다.
• unordered_map은 중복된 데이터를 허용하지 않고, map에 비해 데이터가 많을 시 월등히 좋은 성능을 보입니다.
  (하지만 key가 유사한 데이터가 많으면 해시 충돌로 인해 성능이 떨어질 수 있습니다.)
• 해시 충돌이 많이 발생하는 상황에는 최악으로 O(N)의 시간복잡도를 가질 수있습니다.

map

• Binary Search Tree로 탐색 시간 복잡도는 O(log(n))입니다.
• map은 자료를 저장할때 내부에서 key를 기준으로 정렬하며 오름차순으로 정렬합니다.

결론

• QA

  Unordered_map이 그럼 제일 좋을까??
  저장한 자료가 적을 때에는 메모리 낭비와 검색 시 오버헤드가 생기게 됩니다. 따라서 이런 경우는 vector나 list가 unordered_map보다 빠르게 됩니다.(수 천이상의 자료를 저장할때, unordered_map을 사용하는 것이 좋습니다.)

관련문제: 프로그래머스 베스트앨범

2. 풀이:

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
bool compare(const pair<int,int> &a, const pair<int,int> &b){
    return a.second>b.second;//장르별로 재생 순서 내림차순 정렬.
}

bool compare_total(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;
    unordered_map<string,vector<pair<int,int>>> genre_playlist;  //index와 각각 재생횟수 저장.
    unordered_map<string,int> genre_play_cnt;
    vector<pair<string,int>> genre_play_cnt_v;

    for(int i=0;i<genres.size();i++){
        genre_play_cnt[genres[i]]+=plays[i];//장르별로 총 재생 횟수 계산.
        genre_playlist[genres[i]].push_back(make_pair(i,plays[i]));
    }

    for(auto &k: genre_playlist){//각 장르 안에서 음악 재생 순서대로 내림차순 정렬.
        sort(k.second.begin(),k.second.end(),compare);
    }

    genre_play_cnt_v.assign(genre_play_cnt.begin(),genre_play_cnt.end());
    sort(genre_play_cnt_v.begin(), genre_play_cnt_v.end(),compare_total);//장르를 총 조회수가 많은 순서 내림차순으로 정렬.

    for(int i=0;i<genre_play_cnt_v.size();i++){
        string genre_name=genre_play_cnt_v[i].first;
       for(int j=0; (j<genre_playlist[genre_name].size()) && (j<2) ; j++){
            answer.push_back(genre_playlist[genre_name][j].first);
       }
    }
    
    return answer;
}

읽어 주셔서 감사합니다.🙂