[프로그래머스/Level 3] 베스트앨범 (C++)

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

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

 

풀이

 

어떻게 문제를 해결할 지 로직은 잘 짠것 같은데, 이를 구현하는데 많이 애를 먹었다. 여러개의 벡터를 통해 데이터를 유연하게 옮겨가며 자유자재로 정렬을 사용할 수 있어야하는 문제였습니다.

 

장르별 전체 재생 횟수를 구하기 위해서 unordered_map을 사용하였고, 이를 벡터에 옮겨준 후, 정렬하였습니다. 정렬된 벡터를 이용하여 다시 장르 내에서 많이 재생된 노래와 재생 횟수가 같은 경우 낮은 고유번호를 가진 노래를 앨범에 수록하기 위해 또 다른 벡터를 이용하여 정렬해주었습니다. 

 

전체 코드

 

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

struct Info {
    string g; // 장르, 전체 재생 횟수
    int sum;
    bool operator < (const Info &I) const {
        return sum > I.sum;
    }
};

struct Res {
    int p, num; // 재생 횟수, 고유 번호
    bool operator < (const Res &r) const {
        if(p==r.p) {
            return num < r.num;
        }
        return p > r.p;
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    // 장르별 전체 재생 횟수를 구해준다.
    for(int i=0;i<genres.size();i++) {
        um[genres[i]]+=plays[i];
    }
    
    // 장르별 전체 재생 횟수를 내림차순으로 정렬
    vector<Info> info;
    for(auto pair : um) {
        info.push_back({pair.first, pair.second});
    }
    sort(info.begin(), info.end());
    
    // 장르 내에서 많이 재생된 노래와, 그 수가 같다면 고유 번호를 기준으로 오름차순 정렬
    for(auto pair : info) {
        vector<Res> res; // 장르별로 비교하기 위해 for문 안쪽에 선언
        for(int i=0;i<genres.size();i++) {
            if(pair.g==genres[i]) {
                res.push_back({plays[i], i});
            }
        }
        sort(res.begin(), res.end());
        
        // 2개씩 앨범에 수록
        int cnt=0;
        for(auto r : res) {
            cnt++;
            if(cnt>2) break;
            answer.push_back(r.num);
        }
    }
    
    return answer;
}

 

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

int cmp1(pair<int, string> a, pair<int, string> b) {
    return a > b;
}

int cmp2(pair<int, int > a, pair<int, int> b) {
    if(a.first == b.first) return a.second < b.second;
    return a > b;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    // 장르에 따른 전체 재생 수를 구한다.
    for(int i = 0; i < genres.size(); i++) {
        um[genres[i]] += plays[i];
    }
    
    // 재생 수를 기준으로 내림차순 정렬 
    vector<pair<int, string > > playInfo; // 재생 수, 장르
    for(auto it : um) {
        playInfo.push_back({ it.second, it.first });
    }
    sort(playInfo.begin(), playInfo.end(), cmp1);
    
    
    for(auto p : playInfo) {
        // 장르 별 재생 수와 인덱스 번호를 가진 리스트를 만들고, 2번, 3번 조건에 맞게 정렬
        vector<pair<int ,int > > playList; // 재생 수, 인덱스 번호
        for(int i = 0; i < genres.size(); i++) {
            if(p.second == genres[i]) playList.push_back({ plays[i], i });
        }
        sort(playList.begin(), playList.end(), cmp2);
        
        // 장르 내에서 많이 재생된 노래를 수록한다.
        int cnt = 0;
        for(int i = 0; i < playList.size(); i++) {
            cnt++;
            if(cnt > 2) break;
            answer.push_back(playList[i].second);
        }
    }
    
    return answer;
}