[C++, Hash] 프로그래머스 베스트앨범 문제 풀이

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범 | 프로그래머스

 

풀이

참고하지 않고 스스로 한 번에 풀어서 더욱 뿌듯한 문제이다.

문제 조건을 보면 3가지 기준이 나온다.

 

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서 고유번호가 낮은 노래를 먼저 수록합니다.

 

결국 요약하면 

1. 많이 재생된 장르

2. 많이 재생된 노래

3. 고유번호가 낮은 노래 

순으로 정렬하면 되는 것이다.

 

첫 번째로 많이 재생된 장르를 찾기 위해 unordered_map와 vector, myvec 구조체를 사용하여 정렬하였고 

다음으로 장르 내에서 많이 재생된 노래와 고유번호가 낮은 노래 순으로 정렬하기 위해 vector, ans 구조체를 사용하였다.

 

또한 장르 중에 2개까지 선택하므로 3개가 넘어가면 장르를 넘겼다.

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct myst{
    int sum;
    string s;
    bool operator< (const myst &c )const{
        return sum>c.sum;
    }
};

struct ans{
    int idx;
    int play;
    bool operator<(const ans &a)const{
        if(play==a.play){
            return idx < a.idx;
        }
        return play > a.play;
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int size = genres.size();
    
    //많이 재생된 장르를 찾자!
    unordered_map <string, int> hash;
    vector <myst> vec;
    for (int i = 0 ; i < size ; i++) {
        hash[genres[i]]+= plays[i];
    }
    for (auto pair:hash) {
        vec.push_back({pair.second,pair.first});
    }
    
    sort(vec.begin(),vec.end());
    
    
    for(auto my :vec){
        // 장르내에서 많이 재생된 노래를 찾자!
        // 재생된 순이 같다면 다음 고유번호가 낮은 순으로!
        vector <ans> tmp;
        for (int i=0;i<size;i++) {
            if(my.s==genres[i]){
                tmp.push_back({i,plays[i]});
            }
        }
        
        sort(tmp.begin(),tmp.end());
        int cnt=0;
        for(auto t :tmp){
            cnt++;
            if(cnt>2) break;
            answer.push_back(t.idx);
            
        }
    }
    
    
    return answer;
}