[프로그래머스, C++] 베스트앨범(해시파트)

문제 링크

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

 

 

 

풀이

주석으로 많이 표시해놓았지만, 요약하면 다음과 같다.

 

// init

1. map(중복X)로 장르당 총 횟수를 저장

2. 동시에, multimap(중복O)으로 장르당 고유번호를 저장

 

// 사전처리 - map(중복X)에 장르(string)로 사전 순으로 정렬돼있으므로 횟수 순으로 정렬을 바꿔주기 위한 처리

1. 횟수당 장르로 map으로 다시 저장

- 횟수순으로 알아서 오름차순 정렬된다, 횟수는 고유하다고 문제에 나와있다.

 

2. vector 컨테이너에 거꾸로 넣는다.(rbegin(), rend() 반복자 이용)

 

// process

많이 재생된 장르로 반복문을 돈다(vector 컨테이너 순)

{

    0. 저장해두었던 [장르 - 고유번호(multimap)]의 원소가 1개라면, 바로 push 후 continue;

    1. 2개 이상이면, 임시 vector<pair<횟수, 고유번호>>에 넣어준다.

    2. 임시 vector 컨테이너를 횟수 순으로 정렬(같으면 고유번호가 낮은순)

    3. vector 컨테이너의 앞 두 원소를 넣어줌.

} 

 

 

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

using namespace std;

// 많이 재생된 노래 장르별로 두 개씩

// 1. 속한 노래가 많이 재생된 장르 먼저
// 2. 장르 내에서 많이 재생된 노래 먼저
// 3. 장르 내에서 같은 노래면 고유번호 낮은 것부터 먼저

// 노래의 장르를 나타내는 문자열 배열 genres
// 노래별 재생 횟수를 나타내는 정수 배열 plays
// 고유 번호 i

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

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> g_n;     // 장르(key) - 횟수(value)
    multimap<string, int> g_i;   // 장르(key) - 고유번호(value)
    
    // init
    for(int i=0; i<plays.size(); i++){      // i: 고유번호
        string g = genres[i];       // 장르 명: g
        int num = plays[i];         // 횟수: num
        
        g_n[g] += num;       // 장르 - 횟수 저장(중복 X)
        g_i.insert(make_pair(g, i));        // 장르 - 고유번호 저장
    }
    
    map<int, string> i_g;       // 횟수 - 장르, 모든 장르는 재생된 횟수가 다르니까(고유)
    for(auto e: g_n)
        i_g.insert(make_pair(e.second, e.first));       // 횟수로 정렬
    
    vector<string> v;
    for(auto riter=i_g.rbegin(); riter!=i_g.rend(); riter++)     // 거꾸로 넣기
        v.push_back(riter->second);
    
    // process
    for(auto g: v){
        if(g_i.count(g) == 1){      // 하나일 경우
            answer.push_back(g_i.find(g)->second);
            continue;
        }
        vector<pair<int, int>> n_i;     // 횟수 - 고유번호
        
        // 많이 수록된 장르에서 고르기
        for(auto iter=g_i.lower_bound(g); iter!=g_i.upper_bound(g); iter++){
            int id = iter->second;      // 고유번호
            int num = plays[id];       // 횟수
            n_i.push_back(make_pair(num, id));
        }
        sort(n_i.begin(), n_i.end(), cmp);   // 정렬
        
        answer.push_back(n_i[0].second);
        answer.push_back(n_i[1].second);
    }
    
    return answer;      // 베스트 앨범에 들어갈 노래의 고유 번호 순서대로 리턴
}