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

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

코딩테스트 연습 - 베스트앨범

---

---

풀이 과정

문제를 보자마자 해시를 떠올렸다!

여러 장르들이 존재하는데 조건1) 에 의해 속한 노래가 많이 재생된 장르의 순서를 구해야한다.

그러기 위해 우선 장르를 키값으로 가지는 map을 만들었다.

그리고 이 map의 value값은 총 몇 번 재생되었는지를 나타내야하므로 plays 배열의 값을 더해주었다.

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

그러나 map은 내부에서 자동적으로 key 값을 기준으로 정렬을 한다는 특징을 지닌다. 그러나 문제에서 value값이 큰 순서대로 요구한다.

그러기 위해서 map에 있는 key와 value를 벡터로 옮겨서 정렬을 하였다.

for(auto it=mp.begin();it!=mp.end();it++){
        v.push_back(make_pair(it->first,it->second));
    }
    sort(v.begin(),v.end(),compare);

벡터 v의 first는 map의 key (장르)이고 second는 map의 value(각 장르마다의 총 재생횟수)를 나타낸다.

compare함수를 통해 second를 기준으로 내림차순 정렬을 하였다.

bool compare(pair<string,int> a,pair<string,int> b){
    return a.second > b.second;
}

이제 장르 내에서 많이 재생된 노래를 먼저 수록하고, 이 중에서 재생횟수가 같을 경우 인덱스가 작은 것을 구해야한다.

이번에는 어차피 노래 각각에 대한 정보가 필요하므로 map을 사용하지 않고 그냥 벡터로 (장르이름+재생횟수 + 인덱스)를 담았다.

가장 많이 재생된 노래를 골라야하므로 (재생횟수 내림차순)으로 정렬하고 만약 같을 경우, (인덱스 오름차순)으로 정렬해야한다. 이 정렬 기준을 compare2라고 만들었다.

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

이렇게 정렬이 끝났다면 문제는 다 풀었다!

이제 장르값이 같을 때 해당 인덱스를 답에 넣어주면 된다. 그러나 이때, 가장 많이 재생된 노래를 두개씩 모아라는 조건에 주의해줘야한다. 즉, 한 장르당 인덱스는 최대 두개만 들어갈 수 있다.

이 조건을 다음과 같이 걸쳐 주었다.

for(int i=0;i<v.size();i++){
        int count = 0;
        for(int j=0;j<v2.size();j++){
            if(v[i].first==v2[j].first){
                if(count==2){
                    break;
                }
                answer.push_back(v2[j].second.second);
                count++;
            }
        }
    }

---

소스 코드

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

using namespace std;

bool compare(pair<string,int> a,pair<string,int> b){
    return a.second > b.second;
}

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

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string,int> mp; //장르이름 + 총 재생횟수
    vector<pair<string,int>> v; //장르이름 + 총 재생횟수
    vector<pair<string,pair<int,int>>> v2;//장르이름+재생횟수+인덱스
    for(int i=0;i<genres.size();i++){
        mp[genres[i]]+=plays[i];
        v2.push_back(make_pair(genres[i],make_pair(plays[i],i)));
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        v.push_back(make_pair(it->first,it->second));
    }
    sort(v.begin(),v.end(),compare);
    sort(v2.begin(),v2.end(),compare2);

    for(int i=0;i<v.size();i++){
        int count = 0;
        for(int j=0;j<v2.size();j++){
            if(v[i].first==v2[j].first){
                if(count==2){
                    break;
                }
                answer.push_back(v2[j].second.second);
                count++;
            }
        }
    }    
    return answer;
}