[Hash, 난이도 중상] 프로그래머즈, 베스트앨범

이 문제에서는 문자열을 해쉬 값으로 바꿀 수 있어야 하고, 3중 정렬을 해야 한다. 정렬이 조금 까다로운 점 외에는 특별한 수학적 논리력은 요구되지 않는다.

 

아마 여러 요소를 가지는 벡터의 정렬에 익숙하다면 이 문제는 간단히 풀 수 있을 것이다.

main문 위에 있는 compare, compare2 에 대해서 설명 하겠다. 둘다 비교함수이다.

 

compare

• 같은 장르끼리는 벡터 안에서 서로 인접하게 한다. (장르 구별은 해시값으로 한다.)
• 같은 장르 안에서는 앨범이 조회수가 높은 순으로 정렬 시킨다.
• 조회수가 같다면 고유번호가 낮은 순으로 정렬 시킨다.

이렇게 3중 정렬만 해줘도 나중에 처리가 쉬워진다.

 

compare2

• 장르의 총 조회수가 높은 순으로 정렬 시킨다.

이렇게 2중 정렬을 해주면 장르의 총 조회수가 높은 해시값(장르) 를 먼저 수록하기 편해진다.

 

전체 수행 순서는 이렇다.

1. 각 앨범의 해시값을 구하고 {고유번호, 해시값, 조회수} 를 가지는 albom 구조체를 alboms 벡터에 push

2. compare을 기준으로 sort

3. 정렬된 alboms를 이용하여 장르별로 조회수를 합산하여 {총 조회수, 해시값} pair을 total_views 벡터에 push

4. compare2를 기준으로 sort

5. 정렬된 장르별로 조회수가 높은 Top2 앨범의 고유 번호를 answer 벡터에 push

 

테스트 케이스 15개 모두 통과

 

#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
struct albom{
    int _num;
    int _hash;
    int _views;
};

bool compare(albom a, albom b){
    if(a._hash==b._hash && a._views==b._views) return a._num<b._num;
    else if(a._hash==b._hash) return a._views>b._views;
    else return a._hash < b._hash;
}
bool compare2(pair<int,int> a, pair<int,int> b){
    return a.first>b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    vector<pair<int, int> >total_views;
    vector<albom> alboms;
    
    if(genres.size()==1) {
        answer.push_back(0);
        return answer;
    }
    for(int i=0;i<genres.size();i++){
        int hash=0;
        int power = genres[i].length() - 1;
        for (int j = 0; j < genres[i].length(); j++) {
            hash += ((int)genres[i][j])*pow(2, power - j);
        }
        albom a;
        a._num=i;
        a._hash=hash;
        a._views=plays[i];
        alboms.push_back(a);
    }    
    sort(alboms.begin(),alboms.end(),compare);
    
    int viewsum=alboms[0]._views;
    for(int i=1;i<alboms.size();i++){
        if(alboms[i]._hash!=alboms[i-1]._hash){
            total_views.push_back(make_pair(viewsum,alboms[i-1]._hash));
            viewsum=alboms[i]._views;
        }
        else{
            viewsum+=alboms[i]._views;
        }
        if(i==alboms.size()-1){
            total_views.push_back(make_pair(viewsum,alboms[i]._hash));
        }
    }  
    sort(total_views.begin(),total_views.end(),compare2);

    for(int i=0;i<total_views.size();i++){
        for(int j=0;j<alboms.size()-1;j++){
            if(total_views[i].second==alboms[j]._hash){
                answer.push_back(alboms[j]._num);
                if(alboms[j]._hash==alboms[j+1]._hash){
                    answer.push_back(alboms[j+1]._num);
                    break;
                }
            }
        }
    }
    return answer;
}