프로그래머스 - 베스트 엘범

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

접근

그냥 다중 정렬 문제라고 생각하고 풀었습니다.

구현

총 3개의 자료구조를 사용했습니다.

1. 장르를 key로, 재생회수를 value로 가지는 map
2. pair(장르,재생회수)를 원소로 가지는 vector
3. 장르를 key로, 고유번호를 원소로가지는 vector를 value로 가지는 map

정렬 순서는 다음과 같습니다.

1을 2로 복사 한 후 , 2를 재생회수 기준 내림차순 정렬합니다.

3의 각 value인 vector를 2를 참고하여 정렬합니다. 이때 재생회수 순으로 내림차순 하며 만약 같다면 고유번호 순으로 오름차순 합니다.

이후 2를 참고하여 재생회수가 높은 장르부터 3에 value에 들어있는 상위 2개 원소를 answer에 담습니다. 만약 길이가 1이면 한개만 담습니다.

다음은 코드 전문입니다.

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

using namespace std;
map<string,int> play_n;
vector<pair<string,int>> v;
map<string,vector<int>> g_n;
vector<int> p;
bool cmp1(pair<string, int> x, pair<string, int> y);
bool cmp2(int x,int y);
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    p = plays;
    for(int i = 0 ; i < genres.size(); i++){
        play_n[genres[i]] += plays[i];
        g_n[genres[i]].push_back(i);
    }
    
    for(auto iter = play_n.begin(); iter != play_n.end(); ++iter){
        v.push_back(pair<string, int>(iter->first,iter->second));
    }
    
    sort(v.begin(), v.end(), cmp1);
    
    for(int i = 0; i < v.size(); i++){
        sort(g_n[v[i].first].begin(), g_n[v[i].first].end(), cmp2);
        
        for(int j = 0 ; j < 2; j++){
            answer.push_back(g_n[v[i].first][j]);
            if (g_n[v[i].first].size() == 1) {
                break;
            }
        }
        
        
    }
    
    
    return answer;
}

bool cmp1(pair<string, int> x, pair<string, int> y){
    return x.second > y.second;
}
bool cmp2(int x,int y){
    if (p[x] == p[y]) {
        return x < y;
    }else{
        return p[x] > p[y];
    }
    
}

후기

최단 시간에 풀었습니다. 다만 문제에서 주어진 조건을 처음에 놓쳤습니다.

1. 상위 2개의 노래만 고른다는 것
2. 한개만 들어있는 장르는 한개만 고른다는 것

다음부터 구현 후 문제에 조건을 모두 체크해보아야 겠습니다.