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

베스트앨범

이 문제에서는 정렬이 핵심이다.

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> mp;
    for(int i=0; i<genres.size(); i++) {
        mp[genres[i]] += plays[i];
    }
    
    vector<pair<string, int>> vec(mp.begin(), mp.end());

    sort(vec.begin(), vec.end(), [](pair<string, int>& a, pair<string, int>& b) {
        return a.second > b.second;
    });
    
    for(pair<string, int> p: vec) {
        string now = p.first;
        vector<pair<int, int>> tmp;
        for(int i=0; i<genres.size(); i++) {
            if (genres[i] == now) {
                tmp.push_back({plays[i], i});
            }
        }
        sort(tmp.begin(), tmp.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.first == b.first) {
                return a.second < b.second;
            }
            return a.first > b.first;
        });
        int cnt = 0;
        for(pair<int, int> n: tmp) {
            if (cnt == 2) break;
            answer.push_back(n.second);
            cnt++;
        }
    }
    

    return answer;
}

[문제 정의]

우선 가장 많이 재생된 장르순으로 정렬하기 위해서는 map 정렬이 필요했는데, map 정렬을 하는 법을 까먹어서 찾아보고 풀었다.. (반성하쇼 내 자신)

🔑 map 정렬하기 - vector를 이용한 방법

map을 커스텀 정렬 함수를 이용해 정렬하고 싶으면 map의 키:값 쌍을 pair로 묶어 vector로 옮겨, vector 정렬을 하면 된다.

vector<pair<string, int>> vec(mp.begin(), mp.end());

sort(vec.begin(), vec.end(), [](pair<string, int>& a,
								pair<string, int>& b) {
        return a.second > b.second;
});

map<string, int>로 선언한 mp 변수가 있을 때,
이를 vector에 옮겨서 정렬했다.

이때, 재생횟수가 많은 장르 순으로 정렬되어야 하므로 value값을 기준으로 내림차순 정렬을 했다.

그 후부터는 구현이었다.

    for(pair<string, int> p: vec) {
        string now = p.first;
        vector<pair<int, int>> tmp;
        for(int i=0; i<genres.size(); i++) {
            if (genres[i] == now) {
                tmp.push_back({plays[i], i});
            }
        }
        sort(tmp.begin(), tmp.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.first == b.first) {
                return a.second < b.second;
            }
            return a.first > b.first;
        });
        int cnt = 0;
        for(pair<int, int> n: tmp) {
            if (cnt == 2) break;
            answer.push_back(n.second);
            cnt++;
        }
    }

재생 횟수가 많은 장르가 제일 먼저오므로, 우선 처리가 가능하다.
장르별로 베스트 노래 2곡을 선정하기 위해 임시 배열 tmp를 선언했다.

genres와 plays의 크기가 같으므로 주어진 배열에서 해당 장르일 경우 재생횟수와 노래 고유번호를 쌍으로 묶어 배열에 추가했다.

그 후, tmp 배열을 재생횟수가 많은 순으로 내림차순하되, 재생횟수가 같은 경우는 고유번호가 낮은 곡이 우선 정렬되도록 하였다.

장르별 재생횟수가 많은 2곡만을 출력해야하므로 두 곡의 고유번호를 answer 배열에 담으면 테스트 케이스에서 잘 돌아가는 것을 확인할 수 있다.