프로그래머스_베스트앨범(해시)

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

코딩테스트 연습 - 베스트앨범 | 프로그래머스

해당 문제도 해시 문제로 LV3의 문제였다.

문제 자체의 로직은 크게 어렵지 않았는데 직관적으로 짜려고 하다보니 자료형 자체가 괴상해졌다

map<string, pair<int, vector<int>>> 와 같아 졌는데 이는 장르, < 재생횟수, 인덱스 vector> 로 표현한 것이다.

 

이러한 자료형을 통한 해결 로직은 다음과 같다.

장르에 맞게 재생 횟수를 누적으로 합계를  하여 재생 횟수를 더해서 기록한다.

그리고 장르별 재생 횟수에 맞춰 내림차순 정렬한다.

다음, 해당 장르에 속하는 곡 인덱스를 다시 정렬한다.

이 때, 곡 인덱스 정렬 기준은 해당 곡의 재생 횟수이다.

해당 곡의 재생 횟수를 정렬한 다음 개수에 맞춰 정답 vector에 추가를 하면 된다.

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

bool DESC(pair<string,int> p1, pair<string,int> p2){
    return p1.second > p2.second;
}
bool DESC2(pair<int,int> p1, pair<int,int> p2){
    return p1.second > p2.second;
}
// Map을 통해 장르별 개수를 더해준 다음
// pair에다가 해당 index를 기록
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, pair<int,vector<int>>> mp; // 분류, <개수, 인덱스 배열>
    
    // 분류 기록
    for(int i=0;i<genres.size();i++){
        auto sc = mp.find(genres[i]);
        // 발견
        if(sc != mp.end()){
            (sc->second).first += plays[i]; // 재생횟수 더하기
            (sc->second).second.push_back(i); // index 기록
        }
        // 미발견
        else{
            vector<int> temp_v(1,i); // 1개 i로 초기화
            pair<int, vector<int>> temp_pair(plays[i], temp_v); // pair 초기화
            mp.insert(pair<string,pair<int,vector<int>>>(genres[i],temp_pair)); // 삽입
        }
    }
    
    // 재생 수 내림차순 정렬
    vector<pair<string, int>> vp;
    for(auto m : mp){
        vp.push_back(pair<string,int>(m.first, m.second.first));
    }
    sort(vp.begin(), vp.end(), DESC);
    
    // 해당 재생 수에 맞는 것들 가져와서 상단 두개 가져오기
    for(int i=0;i<vp.size();i++){
        auto sc = mp.find(vp[i].first); // 해당 장르 찾아오기
        
        // 개수가 1개일 경우에는 1개만
        if( sc->second.second.size() == 1)
            answer.push_back(sc->second.second[0]);
        
        // 개수 2개 이상일 경우
        else{
            vector<pair<int,int>> temp_vp;
            for(int i=0; i<sc->second.second.size();i++){
                temp_vp.push_back(pair<int,int>(sc->second.second[i],plays[sc->second.second[i]]));
            }
            sort(temp_vp.begin(), temp_vp.end(), DESC2); // 내림차순 정렬
            answer.push_back(temp_vp[0].first);
            answer.push_back(temp_vp[1].first); // 삽입
        }
    }
    
    return answer;
}