[프로그래머스] 베스트앨범

 

문제 설명

장르별로 가장 많이 재생된 노래들을 최대 2개씩 골라 전체 재생수가 높은 장르 순으로 정렬해서 베스트 앨범을 만드는 문제이다.

세부적인 조건은 아래와 같다.

 

• 장르 전체 재생 수가 많은 순서대로 장르 정렬
• 각 장르 안에서는:
  • 재생 수가 높은 노래 먼저
  • 재생 수가 같으면 고유번호가 낮은 노래 먼저
• 각 장르에서 최대 2곡까지만 수록

 

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

프로그래머스

 

 

풀이 과정

장르명이 문자열로 주어지고 노래를 장르명을 바탕으로 묶고 연산을 수행해야 한다.

따라서, 편의를 위해 아래와 같이 Map을 사용하여 장르명별 인덱스 값을 부여했다.

map<string,int> genreIdx;
int genreCount=0;
    
    for(int i=0;i<n;i++){
        if(genreIdx[genres[i]]==0)
        genreIdx[genres[i]] = genreCount++;
    }

 

이를 바탕으로, 아래와 같이 pair를 활용하여 장르별로 {노래의 고유 번호, 재생 수} 형태로 장르별 재생 수를 저장했다.

vector<vector<pair<int,int>>> v(101);

for(int i=0;i<n;i++){
        int idx = genreIdx[genres[i]]; 
        v[idx].push_back({i,plays[i]});
    }

 

이후, "장르 전체 재생 수가 많은 순서대로 장르 정렬"이라는 문제 조건에 맞추기 위해 고민하다 별도의 컨테이너를 추가하지 않고 기존 v에 장르 전체 재생 수를 추가로 넣고, 내림 차순 정렬을 통해 장르 전체 재생 수를 정렬할 수 있도록 구현했다. 추가적으로, 각 장르 안에서는 재생 수가 높은 노래 먼저 출력하기 위해 vector의 값을 내림차순으로 정렬하는 로직도 추가했다.

 

bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.second==b.second){
        return a.first<b.first;
    }
    return a.second>b.second;
}

bool cmpVec(vector<pair<int,int>> a, vector<pair<int,int>> b){
    int a0 = a[0].second;
    int b0 = b[0].second;
    return a0>b0;
}

for(int i=0;i<n;i++){
        int summ=0;
        for(int j=0;j<v[i].size();j++){
            summ+=v[i][j].second;
        }
        v[i].push_back({-1,summ});
        sort(v[i].begin(),v[i].end(),cmp);
    }
    
    sort(v.begin(),v.begin()+n,cmpVec);

 

마지막으로, 정답 출력을 위해, 문제 조건에 맞게 정렬되어 있는 v에 대해 반복문을 돌며 조건에 맞는 값을 answer에 삽입하는 동작을 구현했다. 여기서, min()을 사용하여 장르별 노래 수가 2개보다 적은 경우에 대한 예외 처리를 구현했다.

 

for(int i=0;i<genreCount;i++){
        for(int j=1;j<=min((int)v[i].size()-1,2);j++){
            answer.push_back(v[i][j].first);
        }
    }

 

 

전체 코드

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


bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.second==b.second){
        return a.first<b.first;
    }
    return a.second>b.second;
}

bool cmpVec(vector<pair<int,int>> a, vector<pair<int,int>> b){
    int a0 = a[0].second;
    int b0 = b[0].second;
    return a0>b0;
}

map<string,int> genreIdx;
vector<vector<pair<int,int>>> v(101);

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int n = genres.size();
    int genreCount=0;
    
    for(int i=0;i<n;i++){
        if(genreIdx[genres[i]]==0)
        genreIdx[genres[i]] = genreCount++;
    }
    for(int i=0;i<n;i++){
        int idx = genreIdx[genres[i]]; 
        v[idx].push_back({i,plays[i]});
    }
    
    for(int i=0;i<n;i++){
        int summ=0;
        for(int j=0;j<v[i].size();j++){
            summ+=v[i][j].second;
        }
        v[i].push_back({-1,summ});
        sort(v[i].begin(),v[i].end(),cmp);
    }
    
    sort(v.begin(),v.begin()+n,cmpVec);

    for(int i=0;i<genreCount;i++){
        for(int j=1;j<=min((int)v[i].size()-1,2);j++){
            answer.push_back(v[i][j].first);
        }
    }
    
    
    return answer;
}