프로그래머스 - 베스트앨범 (C++)

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

프로그래머스

 이번 문제는 주어진 노래들의 장르와 재생 횟수를 이용하여 가장 많이 재생된 장르 순으로, 각 장르마다 재생 횟수가 가장 높은 노래를 최대 두 곡씩 반환하는 문제이다. 이 문제에서 신경써야 할 부분은 노래를 수록하는 기준이다. 배열 genres와 plays의 요소들을 한 번 씩 보면서 장르별 재생 횟수를 기록하고, 또 그 장르에서 가장 재생 횟수가 높은 노래가 무엇인지 비교하며 저장한다. 이 부분만 주의한다면 다른 어려움 없이 풀 수 있는 문제라 생각한다. 이 문제를 풀기 위해 고려한 절차는 다음과 같다.

1. 각 index번째의 장르와 재생 횟수를 정보를 갱신한다.
   1. 만약 이번 장르가 처음 보는 장르라면 장르를 저장한다.
   2. 저장되어 있던 이 장르의 재생 횟수에 현재 노래의 재생 횟수를 더한다.
   3. 현재 저장된 '이 장르에서 가장 재생 횟수가 높은 노래들'의 상황에 따라 정보를 갱신한다.
      1. 만약 아직 저장된 노래가 없다면, 이 노래의 정보를 그냥 저장한다.
      2. 만약 저장된 노래가 하나라면, 그 노래와 이 노래의 재생 횟수를 비교하여 적절한 위치에 저장한다.
      3. 만약 저장된 노래가 두 곡이라면, 그 두 노래의 재생 횟수와 현재 노래의 재생 횟수를 비교하여 적절한 위치에 저장한다. 만약, 현재 노래의 재생 횟수가 가장 작다면 저장하지 않는다.
2. 장르별 재생 횟수에 따라 장르를 저장해둔 배열을 정렬한다.
3. 정렬된 장르에 따라 노래 정보를 answer에 저장한다.

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

#define CASE 1

map<string, int> playByGenre;	// 장르별 재생된 횟수
map<string, vector<pair<int, int>>> maxPlays;   // 각각의 장르마다 재생횟수가 높은 노래 두 곡 저장
vector<string> genreList;	// 장르 당 가장 재생 많이 된 노래 두 개

// 재생 횟수 기준 내림차순으로 정렬하기 위한 함수
bool Compare(string a, string b)
{
	if (playByGenre[a] > playByGenre[b])
		return true;
	else
		return false;
}

vector<int> solution(vector<string> genres, vector<int> plays)
{
	vector<int> answer;	
    
    // 1. 각 index번째의 장르와 재생 횟수를 정보를 갱신한다.
	for (int idx = 0; idx < genres.size(); ++idx)
	{
		string genre = genres[idx];
		int play = plays[idx];
        
		// 1-1. 만약 처음 보는 장르라면 장르 리스트에 추가.
        // 1-2. 저장되어 있던 이 장르의 재생 횟수에 현재 노래의 재생 횟수를 더한다
		if (playByGenre[genre] == 0)
			genreList.push_back(genre);
		playByGenre[genre] += play;
        
        // 1-3. 현재 저장된 '이 장르에서 가장 재생 횟수가 높은 노래들'의 상황에 따라 정보를 갱신한다.
		if (maxPlays[genre].size() == 0)
        {
            // 1-3-1. 만약 아직 저장된 노래가 없다면, 이 노래의 정보를 그냥 저장한다.
            maxPlays[genre].push_back({ play, idx });
        }
		else if (maxPlays[genre].size() == 1)
		{
            // 1-3-2. 만약 저장된 노래가 하나라면, 그 노래와 이 노래의 재생 횟수를 비교하여 적절한 위치에 저장한다.
			if (maxPlays[genre][0].first < play)
			{
				pair<int, int> temp = maxPlays[genre][0];
				maxPlays[genre][0] = { play, idx };
				maxPlays[genre].push_back(temp);
			}
			else
				maxPlays[genre].push_back({ play, idx });
		}
		else if (maxPlays[genre].size() == 2)
		{
            // 1-3-3. 만약 저장된 노래가 두 곡이라면, 그 두 노래의 재생 횟수와 현재 노래의 재생 횟수를 비교하여 적절한 위치에 저장한다. 만약, 현재 노래의 재생 횟수가 가장 작다면 저장하지 않는다.
			if (maxPlays[genre][0].first < play)
			{
				pair<int, int> temp = maxPlays[genre][0];
				maxPlays[genre][0] = { play, idx };
				maxPlays[genre][1] = temp;
			}
			else if (maxPlays[genre][1].first < play)
				maxPlays[genre][1] = { play, idx };
		}
	}

    // 2. 장르별 재생 횟수에 따라 장르를 저장해둔 배열을 정렬한다.
	sort(genreList.begin(), genreList.end(), Compare);
    
    // 3. 정렬된 장르에 따라 노래 정보를 answer에 저장한다.
	for (int i = 0; i < genreList.size(); ++i)
	{
		string genre = genreList[i];

		for (int p = 0; p < maxPlays[genre].size(); ++p)
			answer.push_back(maxPlays[genre][p].second);
	}

	return answer;
}