프로그래머스 문제 - 베스트앨범

프로그래머스 베스트앨범 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

고유 번호로 구분된 노래들을 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려고 한다.
수록 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 출력해야 합니다.

문제 풀이

노래들을 기준에 맞추어 졍렬하기 위해서는 몇 가지를 정렬하여 놓아야합니다.
1. 각 장르들의 재생된 노래 수 저장 후 내림차순 정렬
2. 장르 내의 노래들을 많이 재생된 순과 고유 번호를 저장 후 재생된 순을 기준으로 내림차순 정렬

장르들을 빠르게 찾아내기 위하여 해쉬를 사용하는 unordered_map을 사용하였으며 재생 수와 고유 번호들의 저장을 위해 구조체 내에 컨테이너를 생성하였습니다.

정렬을 끝마쳤다면 장르들을 순서대로 출력하되 장르 내의 노래들을 많이 재생된 순 2개까지만 수록되도록 고유 번호들을 넣어줍니다. 1개라면 1개만 수록됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

struct genreMusic
{
    //first : 재생 횟수, second : 인덱스
    vector<pair<int, int>> playidx;
    int totalPlays;
};

bool compare(pair<int, int> a, pair<int, int> b)
{ 
    if(a.first > b.first || a.first == b.first && a.second < b.second)
    {
        return true;
    }
    return false;
}

bool genreCompare(pair<string, genreMusic> a, pair<string, genreMusic> b)   { return a.second.totalPlays > b.second.totalPlays; }

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, genreMusic> genre;
    
    int idx = 0;
    for(string s : genres)
    {
        auto iter = genre.find(s);
        if(iter != genre.end())
        {
            iter->second.playidx.emplace_back(make_pair(plays[idx], idx));;
            iter->second.totalPlays += plays[idx];
        }else
        {
            genreMusic t;
            t.playidx.emplace_back(make_pair(plays[idx], idx));
            t.totalPlays = plays[idx];
            genre.emplace(make_pair(s, t));
        }
        idx++;
    }
    
    //정렬을 위해 벡터로 변환
    vector<pair<string, genreMusic>> vec;
    for(auto iter : genre)
    {
        vec.emplace_back(make_pair(iter.first, iter.second));
    }
    
    //plays의 합을 기준으로 내림차준
    sort(vec.begin(), vec.end(), genreCompare);
    
    for(pair<string, genreMusic> g : vec)
    {
        sort(g.second.playidx.begin(), g.second.playidx.end(), compare);
        for(int i = 0; i < g.second.playidx.size(); i++)
        {
            if(i == 2)  break;
            answer.emplace_back(g.second.playidx[i].second);
        }
    }
    
    return answer;
}

출저

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