[HASH]베스트 앨범

 

문제 풀이할때, 제한사항을 잘 읽어야한다.

장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다** 이런 조건들을 잘 확인하여 예외처리 구문이 들어가야함.

 

출력

 

노래의 장르를 나타내는 문자열 배열 genres와 
노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 
베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

 

접근

 

작업 조건

 

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

 

정의

 

판단 기준 자료구조 정리
장르(고유번호, 재생 수)

1) 가장 많이 재생된 장르 수록
2) 장르 내에서 가장 많이 재생된 노래 수록
3) 장르 내에서 재생 횟수가 같은경우 고유번호 낮은 노래 수록.alignas
 - sort하여 처리 진행 필요. 혹은 map 사용.

 

답 1)

 

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    unordered_map<string,int> music;
    unordered_map<string,map<int,int>> musiclist;
    for(int i=0;i<genres.size();i++)
    {
        music[genres[i]]+=plays[i];
        musiclist[genres[i]][i]=plays[i];
    }

    while(!music.empty())
    {
        int max=0;
        string max_genre;
        //music에서 가장큰값.
        for(auto& genre : music)
        {
            if(max<genre.second)
            {
                max=genre.second;
				max_genre=genre.first;
			}
        }

        //music list에서 genre의 맨앞두개 push
        for(int i=0;i<2;i++)
        {
            int max_val=0;
            int idx=-1;

			for (auto &ml : musiclist[max_genre])
			{
				if (max_val < ml.second)
				{
					max_val =ml.second;
					idx = ml.first;
				}
			}
            if(idx==-1)
                continue;
			musiclist[max_genre].erase(idx);
            answer.push_back(idx);
        }
        music.erase(max_genre);
    }


    return answer;
}

 

 

#시행착오 1

 

문제풀이시, 한 장르 내의 재생수를 기준으로 자동 정렬이 되어있다면 더 효율적으로 계산 가능할것이라 생각했다.

따라서 map의 자동 sort 기능을 활용해보려 musiclist내부의 map을<plays,idx,greater<>> 로 선언해줬다.

결과는 정확도가 98%로 틀리게된다.

 

원인은 해당 알고리즘의 경우 key가 play 횟수로 설정되는데, 이때 key 값이 중복되는경우의 수가 발생한다.

중복되는경우 동일 key값의 이전 경우의 수가 삭제되기 때문에 문제가발생한다.

 

따라서 map에서 key 값을 설정할 때, key는 중복되지 않는 값으로 설정해줘야한다.

 

코드

vector<int> solution2(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    unordered_map<string,int> music;
    unordered_map<string,map<int,int,greater<>>> musiclist;
    for(int i=0;i<genres.size();i++)
    {
        music[genres[i]]+=plays[i];
        musiclist[genres[i]][plays[i]]=i;
    }

    while(!music.empty())
    {
        int max=0;
        string max_genre;
        //music에서 가장큰값.
        for(auto& genre : music)
        {
            if(max<genre.second)
            {
                max=genre.second;
				max_genre=genre.first;
			}
        }

        //music list에서 genre의 맨앞두개 push
        int i=0;
		for (auto &ml : musiclist[max_genre])
		{
			if (i > 1)
				break;
			else
			{
				answer.push_back(ml.second);
				i++;
			}
		}
		music.erase(max_genre);
    }


    return answer;
}

 

 

#시행착오 2

 

*** 비교 판단을 진행할때, 비교 판단에 사용되는 temp값들은 회차별로 초기화를 시켜줘야한다.

ex)  배열 내의 max값들을 찾아서 추출해내는 작업.

-> 비교 판단에 사용되는 값 : idx, max

-> 새로운 비교판단을 진행하기 전 초기화 작업 진행해줘야함.

for(int i=0;i<2;i++)
{
    max = 0;
    int idx = -1;

    for (auto val : musics[max_genre])
    {
        if (max < val.second)
        {
            max = val.second;
            idx = val.first;
        }
    }

    if(idx==-1)
        continue;
    musics[max_genre].erase(idx);
    answer.push_back(idx);
}

 

 

#시행착오 3

 

- 각 장르 변수와 장르별 재생수 변수는 선언하였으나, 장르 내에서 최대값을 구하는 방법을 구현하지 못했음.

 

** 개념화 부족

• 개념화가 명확하게 준비되지 않은 상태에서 구성시 항상 문제가 발생함.
• 따라서 개념화를 명확히 진행 후 수행해야함.

<HASH 구조에서 최대/최소값 찾는 방법>

 

- hash 문제에서 최대/최소값을 순회하며 구하기 위해선 현재 최대/최소값을 구한 후, 해당 값을 erase 하는 방식으로 진행해야한다. Map은 반복자가 없기때문에 sort로 정렬이 불가능하기 때문이다.

 

 

1차 개념화

1. 장르별 우선순위 파악
2. 장르내에 우선순위 파악
3. 우선순위에 따라 정렬.

구현 방법)

 

1) 장르별 우선순위 파악

• Map 선언하여, 장르별 재생값 파악.
• Map 내에서 최대값을 파악하는 방법 => map은 반복자가 없기에 sort 불가능.
• 따라서 최댓값을 구한 후, 제거하는 방식으로 반복 진행.

2) 장르 내에 우선순위 파악.

 

• 장르 우선, 재생 수 우선, 재생수 같을시 고정번호 우선.
• Map<genre,vector<고정번호,재생수>> 선언하여 장르별 재생수 리스트 파악할수 있도록 설정.
• 장르 별 재생순위 비교하여 판단 진행.
• => 선택 장르의 최대 재생수 변수 파악.
• => 결과 배열에 해당 변수의 고정번호 인가
• => 최대 재생수 리스트 삭제
• => 2회 반복
• => 만약 2회보다 리스트 수가 적을시, 1번만 진행. // 초기화값

#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(vector<string> genre, vector<int> plays)
{
    vector<int> res;

    //map 변수 선언 장르//고유번호, 재생수
    unordered_map<string,vector<pair<int,int>>> album;
    map<string,int> genre_num;

    for(int i=0;i<genre.size();i++)
    {
        album[genre[i]].push_back({i,plays[i]});
        genre_num[genre[i]] +=plays[i];
    }

    // 큰 장르부터 진행.
    // 장르 내에서는 순서대로 최대 2개까지 
    
    while(!genre_num.empty())
    {
        string max_g;
        int max_play=0;
        for(auto g : genre_num)
        {
            if(max_play<g.second)
            {
                max_play=g.second;
                max_g = g.first;
            }
        }
        genre_num.erase(max_g);//**** */

        //해당 장르에서 맥스값.
        for(int i=0;i<2;i++)
        {
            int max_val=0;
            int max_idx=-1;
            int max_idx_j=-1;
            for(int j=0;j<album[max_g].size();j++)
            {
                if(max_val<album[max_g][j].second)
                {
                    max_val=album[max_g][j].second;
                    max_idx=album[max_g][j].first;
                    max_idx_j=j;
                }
            }
            if(max_idx==-1)
                continue;
            album[max_g].erase(album[max_g].begin()+max_idx_j);
            res.push_back(max_idx);
        }
    }

    return res;
}