Coding Test] 베스트 앨범 문제(Hash)

[Programmers School 문제 링크]

• 수록(장르별로 최대 2곡) 순서 기준

1. 많이 재생된 장르

2. 많이 재생된 노래

3. 고유 번호가 낮은 노래

• Code

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

//map<장르, pair<전체 재생 횟수, 장르에 속하는 노래 인덱스들>>
map<string, pair<int, vector<int>>> all;

//all[장르].(전체 재생 횟수) 비교
bool CompareTotalPlays(string a, string b)
{
    return all[a].first > all[b].first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    //장르 종류 저장(나중에 재생 횟수가 많은 장르 별로 정렬)
    vector<string> gen;
    for(int i = 0; i < genres.size(); i++)
    {   
        if(all.find(genres[i]) == all.end()) //기존에 없던 장르면 새로 추가
        {
            gen.push_back(genres[i]);
            all.insert({genres[i], make_pair(plays[i], vector<int>{i})});
        }
        else //기존에 있던 장르면 재생 횟수 증가
        {
            all[genres[i]].first += plays[i];
            all[genres[i]].second.push_back(i);
        }
    }
    
    //1. 많이 재생된 장르
    sort(gen.begin(), gen.end(), CompareTotalPlays);
    
    //장르 내 정렬 시작
    vector<int> answer;
    for(int cur_gen = 0; cur_gen < gen.size(); cur_gen++)
    {
        map<int, vector<int>> play; //map   <재생 횟수, 노래 인덱스들>
        vector<int> cur_plays;      //vector<재생 횟수>
        
        //이번 장르에 속한 노래 인덱스 순회
        vector<int> indexs = all[gen[cur_gen]].second;
        for(int i = 0; i < indexs.size(); i++)
        {
            int playCount = plays[indexs[i]];   //재생 횟수
            int musicIdx = indexs[i];           //노래 인덱스
            
            //Add values
            if(play.find(playCount) == play.end())  //신규
            {
                play.insert({ playCount, { musicIdx } });
                cur_plays.push_back(playCount);
            }
            else                                    //중복
            {
                play[playCount].push_back(musicIdx);
            }
        }
        
        //2. 많이 재생된 노래
        sort(cur_plays.begin(), cur_plays.end(), greater<int>());
        
        for(int i = 0; i < 2 && i < cur_plays.size(); i++)
        {
            //3. 고유 번호가 낮은 노래
            sort(play[cur_plays[i]].begin(), play[cur_plays[i]].end());
            
            //노래 수록
            answer.push_back(play[cur_plays[i]][0]);
            
            //중복된 노래가 있음 && 수록 여유있음
            if(play[cur_plays[i]].size() > 1 && i + 1 < 2)
                answer.push_back(play[cur_plays[i++]][1]);
        }
    }
    return answer;
}

---

• 알고리즘 동작 설명

0. Input

genres { 장르1, 장르2, 장르2, 장르1, 장르3, 장르1 }

plays { 800, 2000, 10, 800, 5000, 1000 }

{ 노래1 노래2 노래3 노래4 노래5 노래6 }

1. 많이 재생된 장르

//map<장르, pair<전체 재생 횟수, 장르에 속하는 노래 인덱스들>>
map<string, pair<int, vector<int>>> all;

//all[장르].(전체 재생 횟수) 비교
bool CompareTotalPlays(string a, string b)
{
    return all[a].first > all[b].first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    //장르 종류 저장
    vector<string> gen;
    for(int i = 0; i < genres.size(); i++)
    {   
        if(all.find(genres[i]) == all.end()) //기존에 없던 장르면 새로 추가
        {
            gen.push_back(genres[i]);
            all.insert({genres[i], make_pair(plays[i], vector<int>{i})});
        }
        else //기존에 있던 장르면 재생 횟수 증가
        {
            all[genres[i]].first += plays[i];
            all[genres[i]].second.push_back(i);
        }
    }    
    //1. 많이 재생된 장르
    sort(gen.begin(), gen.end(), CompareTotalPlays);

    ...
    return answer;
}

장르별로 정렬

장르 1 (map<장르 1, pair<2600번, { 노래 1, 노래 4, 노래 6 } > )

합계 = 2600번

노래 1 = 800번

노래 4 = 800번

노래 6 = 1000번

장르 2 (map<장르 2, pair<2010번, { 노래 2, 노래 3 })

합계 = 2010번

노래 2 = 2000번

노래 3 = 10번

장르 3 (map<장르 3, pair<5000번, { 노래 5 })

합계 = 5000번

노래 5 = 5000번

장르 우선 순위 정렬 vector<int> gen;

장르 3(5000) > 장르 1(2600) > 장르 2(2010)

• 설명

vector<string> gen에 장르들을 중복없이 저장하면서

map 변수 all에 각 장르의 총 재생 횟수와 노래의 인덱스를 저장한 뒤

vector gen을 all[이번 장르]의 총 재생 횟수를 기준으로 정렬한다.

2. 장르 내 우선순위

vector<int> solution(vector<string> genres, vector<int> plays) {
    ...
    ...
    
    //장르 내 정렬 시작
    vector<int> answer;
    for(int cur_gen = 0; cur_gen < gen.size(); cur_gen++)
    {
        map<int, vector<int>> play; //map   <재생 횟수, 노래 인덱스들>
        vector<int> cur_plays;      //vector<재생 횟수>
        
        //이번 장르에 속한 노래 인덱스 순회
        vector<int> indexs = all[gen[cur_gen]].second;
        for(int i = 0; i < indexs.size(); i++)
        {
            int playCount = plays[indexs[i]];   //재생 횟수
            int musicIdx = indexs[i];           //노래 인덱스
            
            //Add values
            if(play.find(playCount) == play.end())  //신규
            {
                play.insert({ playCount, { musicIdx } });
                cur_plays.push_back(playCount);
            }
            else                                    //중복
            {
                play[playCount].push_back(musicIdx);
            }
        }
        
        //2. 많이 재생된 노래
        sort(cur_plays.begin(), cur_plays.end(), greater<int>());
        
        

장르 내 재생 횟수 순으로 정렬

장르 3 { 노래 5 }

장르 1 { 노래 6, 노래 4, 노래 1 }

장르 2 { 노래 2, 노래 3 }

• 설명

장르 순서가 정렬된 vector<string> gen을 순회하는 for문 안에서 play, cur_plays 변수에 필요한 데이터를 저장한다.

- map<int, vector<int>> play : 중복가능한 재생 횟수를 Key에 같은 재생 횟수를 가지고 있는 노래의 인덱스 들을 저장

- vector<int> cur_plays : 재생 횟수 순으로 정렬하기 위한 vector에 재생 횟수를 중복없이 저장

그 뒤 재생 횟수를 내림차순으로 정렬한다.

3. 재생 횟수가 같은 경우 낮은 고유 번호 순으로 정렬, 노래 수록

vector<int> solution(vector<string> genres, vector<int> plays) {
    ...
    ...
    //장르 내 정렬 시작
    vector<int> answer;
    for(int cur_gen = 0; cur_gen < gen.size(); cur_gen++)
    {
        ...
        ...
        
        for(int i = 0; i < 2 && i < cur_plays.size(); i++)
        {
            //3. 고유 번호가 낮은 노래
            sort(play[cur_plays[i]].begin(), play[cur_plays[i]].end());
            
            //노래 수록
            answer.push_back(play[cur_plays[i]][0]);
            
            //중복된 노래가 있음 && 수록 여유있음
            if(play[cur_plays[i]].size() > 1 && i + 1 < 2)
                answer.push_back(play[cur_plays[i++]][1]);
        }
    }
    return answer;
}

재생 횟수가 큰 순으로 정렬된 노래들 중 동일한 재생 횟수인 노래들을 고유번호의 오름차순으로 정렬

장르 3

노래 5

장르 1

노래 6 > 노래 1 > 노래 4(장르 1의 세번째 곡이라 수록되지 않음)

장르 2

노래 2 > 노래 3

노래 수록

answer { 노래 5, 노래 6, 노래 1, 노래 2, 노래 3 }

• 설명

노래는 장르별로 2 곡 까지 수록할 수 있다.

재생 횟수의 큰 순으로 정렬된 vector<int> cur_plays를 순회하며 이번 재생 횟수(cur_plays[i])를 재생 횟수별 노래들의 인덱스를 저장해두었던 map<int, vector<int>> play에서 이번 재생 횟수와 동일한 노래들을 고유번호 순서로 정렬한다.

그런 뒤 play[cur_plays[i][0]에 있는 노래를 수록(answer.push_back(...))하고, 만약 동일한 재생 횟수인 노래가 두곡 이상이고, 이번 장르의 수록 횟수가 남았다면 다음 노래(play[cur_plays[i][1])를 저장하고, i를 1 올려준다.

모든 반복문이 종료되면 수록된 목록을 반환해준다.