[프로그래머스] 베스트앨범 (feat. Hash)

이전에 N사 코딩테스트를 봤을 때 해시를 잘 다루지 못해 그런 아쉬움으로 해시 연습 삼아 다시 풀어보았다.

 

우선순위: 장르별 재생 횟수 내림차순 - 장르 내 재생 횟수 내림차순 - 고유번호 오름차순

 

노래의 장르를 나타내는 문자열 배열: genres

노래별 재생 횟수를 나타내는 정수 배열: plays

 

이렇게 되면 추가적으로 필요한 자료 구조

- 장르별 전체 재생 횟수 저장

- 장르별 곡당 재생 횟수: 곡별로 재생횟수를 저장해야하므로 value에는 vector어야 한다.

 

이렇게 문제를 까고 보면 어렵지 않은데 막상 해시를 여러 개 써야하는 순간이 오면 굉장히 헷갈린다...

따라서 헷갈리지 않고 어떤 자료구조를 써야하는지를 유심히 고민하고, 헷갈리지 않는다면 쉽게 풀 수 있을 것 같다.

 

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(i, plays[i]));
}

장르별로 재생횟수를 증가하고, 이제 장르 내에서 곡 번호와 재생횟수를 같이 저장한다.

vector <pair<int,string>> order;
for(auto genre : summap){           //재생 수가 가장 높은 장르 오름차순 sort
    order.push_back(make_pair(genre.second, genre.first));
}
sort(order.begin(), order.end());

 

 

앞에서 사용한 자료구조는 장르명(string) : 장르별 재생횟수(int)로 저장되었다면,

이번에는 key, value를 뒤집어 장르별 재생횟수(int) : 장르명(string)으로 저장한다.

이렇게 하는 이유는 총 재생 수 내림차순으로 장르를 파악하기 위함으로 sort를 한다.

뒤에서부터 접근하면 된다.

while(order.size()!=0){
    pair <int, string> temp = order.back();
    order.pop_back();
    vector <pair<int,int>> songs = genmap[temp.second];
    //해당 장르의 곡 인덱스와 재생수 가져온다
    sort(songs.begin(), songs.end(), cmp);
    if(songs.size() == 1){
        answer.push_back(songs[0].first);
    }
    else {
        answer.push_back(songs[0].first);
        answer.push_back(songs[1].first);
    }

}

이렇게 아까 장르별 곡들을 파악하기 위해 벡터를 value로 삼는 해시맵 genmap 을 이용해 value였던 곡 인덱스와 재생횟수를 파악한다.

cmp함수를 써서 second값을 최우선순위로 정렬을 하였다.

 

🚨 여기서 주의할 점은 장르별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 한 장르에는 최대 2개의 곡만 존재한다. 따라서 불편하게 for문을 돌릴 필요가 없고, 그렇게 해서도 안된다.