프로그래머스 / 베스트앨범

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

프로그래머스

 

장르의 이름(key)과 재생 횟수(value)를 이용하여야 하기 때문에 unordered_map 자료구조를 이용했다

그리고 총 재생 횟수대로 정렬을 하기 위해 vector도 사용했다

 

    // 장르의 이름(key)과 재생 횟수와 인덱스(value)를 저장하는 unordered_map
	unordered_map<string, vector<pair<int, int>>> umGenres; 
    // 장르의 이름(key)과 총 재생 횟수(value)를 저장하는 unordered_map
	unordered_map<string, int> umPlay;           
    // 장르의 이름과 총 재생 횟수를 저장하는 vector
	vector <pair<string, int>> vOrder;

 

먼저 umGenres는 한 장르(key)마다 가지고 있는 곡(value)의 재생 횟수와 인덱스(pair<int,int>)를 값으로 갖는다

그리고 vOrder는 장르와 총 재생 횟수를 pair로 묶어서 보관하고 정렬을 하기 위해 선언했다

umPlay는 장르를 빠르게 탐색할 수 있기 때문에 사용했다. umPlay 없이 바로 vOrder에 삽입을 하려고 하면 삽입할 때 마다 매번 vOrder는 새로운 값의 장르가 기존에 존재하는지 확인해야 하고 이는 평균 O(N)의 탐색시간을 갖는다

하지만 umPlay를 이용하면 unordered_map의 특성상 해시를 이용하기 때문에 평균 O(1)의 탐색시간으로 별도의 저장공간은 필요하지만 삽입시 탐색시간을 매우 단축시킬 수 있기 때문에 사용했다

장르의 종류가 많아질수록 unordered_map을 이용하면 장르를 평균 O(1)에 탐색할 수 있어 효율적이다

 

    for (int i = 0; i < genres.size(); i++)
    {
		umGenres[genres[i]].push_back(make_pair(plays[i], i));
		umPlay[genres[i]] += plays[i];
    }

    for (auto it = umPlay.begin(); it != umPlay.end(); it++)
    {
		vOrder.push_back(make_pair(it->first, it->second));
    }

 

장르의 사이즈(곡의 수)만큼 순회하여 모든 곡을 umGenres[곡의 장르 이름]에 pair<재생 횟수,인덱스>를 넣고

umPlay[곡의 장르 이름]의 value에 plays(재생 횟수)를 더해준다

unordered_map에 연산자를 사용하면 따로 초기화를 하지 않아도 기본값으로 초기화가 되기 때문에

umPlay를 따로 초기화 하지 않았지만 새로운 장르 이름을 umPlay에 삽입할 때 int의 기본값인 0으로 초기화가 되면서 0 += plays[i]가 적용된다

umGenres와 umPlay를 모두 삽입한 후에는 umPlay에 이미 저장된 총 재생 횟수를 vector인 vOrder에 저장하여 정렬할 수 있게 한다

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

 

위와 같은 조건에 맞춰 정렬하면 다음과 같다

    // 총 재생 횟수가 높은 장르를 먼저 수록하도록 정렬
    sort(vOrder.begin(), vOrder.end(),
        [](const pair<string, int>& a, const pair<string, int>& b)
        {
            return a.second > b.second;
        });

	// 장르 내에서 재생 횟수가 같은 경우 인덱스가 낮은 노래를 먼저 수록하도록 정렬
    for (auto it = umGenres.begin(); it != umGenres.end(); it++)
    {
        sort(it->second.begin(), it->second.end(),
            [](const pair<int,int>& a, const pair<int,int>& b)
            {
                // 재생 횟수가 같으면
                if (a.first == b.first)
                {
					// 인덱스가 낮은 노래를 먼저 수록하도록 정렬
                    return a.second < b.second;
                }
                // 재생 횟수가 다르면
                else
                {
					// 재생 횟수가 높은 노래를 먼저 수록하도록 정렬
                    return a.first > b.first;
                }
            });
    }

 

여기서 중요한 점은 unordered_map<string, vector<pair<int, int>>> umGenres; 에서 unordered_map은 정렬이 불가능 하지만 value인 vector<pair<int,int>>는 정렬이 가능하다는 것이다.

위의 sort함수는 vOrder를 정렬하는것이고 밑의 for문의 sort함수는 unordered_map의 value를 정렬하는 것이다

 

먼저 vOrder를 총 재생 횟수(vOrder.second)가 가장 많은 장르부터 정렬했다

unordered_map은 인덱스로 접근이 불가능 하기 때문에 umGenres의 value인 vector<pair<int,int>>는 iterator를 이용하여 순회하며 정렬했다

vector<pair<int,int>> 를 정렬할 땐 각 곡의 재생 횟수가 같은 경우 umGenres[장르이름][재생크기순번].second(이 경우 인덱스를 의미한다)가 낮은 순서대로 정렬하고 재생횟수가 다른 경우에는 umGenres[장르이름][재생크기순번].first(재생 횟수)가 큰 순서대로 정렬했다

	int maxNum = 2;  // 장르별 최대 수록 곡 수

    // answer에 입력
    for (int i = 0; i < vOrder.size(); i++)
    {
        if (umGenres[vOrder[i].first].size() == 1)
        {
			answer.push_back(umGenres[vOrder[i].first][0].second);
        }
        else
        {
            for (int j = 0; j < maxNum; j++)
            {
                answer.push_back(umGenres[vOrder[i].first][j].second);
            }
        }
    }

 

먼저 int maxNum을 선언하여 값을 따로 조정할 수 있게 했다

그 다음 총 장르의 수만큼 순회하며 vOrder[i].first는 장르의 이름(string)을 의미하니

umGenres[장르의 이름]의 size가 1인 경우를 따로 분리하여 곡이 하나뿐인 장르에서 존재하지 않는 두 번째 곡에 접근하는 것을 방지했다

else문으로 같은 장르의 곡이 2개 이상인 경우 for문으로 maxNum만큼 순회하여 해당 장르를 maxNum만큼 삽입하게 했다

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

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

    // 장르의 이름(key)과 재생 횟수와 인덱스(value)를 저장하는 unordered_map
	unordered_map<string, vector<pair<int, int>>> umGenres;     
    // 장르의 이름(key)과 총 재생 횟수(value)를 저장하는 unordered_map
	unordered_map<string, int> umPlay;                          
    // 장르의 이름과 총 재생 횟수을 저장하는 vector
	vector <pair<string, int>> vOrder;                          

    // 삽입
    for (int i = 0; i < genres.size(); i++)
    {
		umGenres[genres[i]].push_back(make_pair(plays[i], i));
		umPlay[genres[i]] += plays[i];
    }
    
    for (auto it = umPlay.begin(); it != umPlay.end(); it++)
    {
		vOrder.push_back(make_pair(it->first, it->second));
    }

    // 총 재생 횟수가 높은 장르를 먼저 수록하도록 정렬
    sort(vOrder.begin(), vOrder.end(),
        [](const pair<string, int>& a, const pair<string, int>& b)
        {
            return a.second > b.second;
        });

	// 장르 내에서 재생 횟수가 같은 경우 인덱스가 낮은 노래를 먼저 수록하도록 정렬
    for (auto it = umGenres.begin(); it != umGenres.end(); it++)
    {
        sort(it->second.begin(), it->second.end(),
            [](const pair<int,int>& a, const pair<int,int>& b)
            {
                // 재생 횟수가 같으면
                if (a.first == b.first)
                {
					// 인덱스가 낮은 노래를 먼저 수록하도록 정렬
                    return a.second < b.second;
                }
                // 재생 횟수가 다르면
                else
                {
					// 재생 횟수가 높은 노래를 먼저 수록하도록 정렬
                    return a.first > b.first;
                }
            });
    }

	int maxNum = 2;  // 장르별 최대 수록 곡 수

    // answer에 입력
    for (int i = 0; i < vOrder.size(); i++)
    {
        // 장르에 곡이 1개인 경우 없는 곡을 찾는걸 방지하기 위해 한번만 push_back
        if (umGenres[vOrder[i].first].size() == 1)
        {
			answer.push_back(umGenres[vOrder[i].first][0].second);
        }
        // 장르에 곡이 2개 이상인 경우
        else
        {
            // maxNum만큼 push_back
            for (int j = 0; j < maxNum; j++)
            {
                answer.push_back(umGenres[vOrder[i].first][j].second);
            }
        }
    }

    return answer;
}