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

문제

프로그래머스 해시 - 베스트앨범 (Level 3)

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

 

---

문제 풀이

접근 방식

아래의 기준에 따라 베스트 앨범에 곡을 수록할 때,

베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하는 문제이다.

 

베스트 앨범의 노래 수록 기준

 

우선, 장르별 총 재생 수를 알아야 1번 기준을 충족시킬 수 있기 때문에

unordered_map을 사용하여 장르별 총 재생 수를 구해주었다.

 

위의 결과를 이용하여 result 벡터에 각 노래의 장르별 총 재생 수, 노래 재생 수, 노래 고유 번호를 저장해주었다.

그 후, 장르별 재생 수 기준 내림차순, 노래 재생 수 기준 내림차순,

고유 번호 기준 오름차순으로 정렬하는 cmp 함수를 아래와 같이 만들어 result 벡터를 정렬해주었다.

bool cmp(const vector<int> &A, const vector<int> &B){    
    if(A[0] > B[0])
        return true;
    else if (A[0] == B[0]){
        if(A[1] > B[1])
            return true;
        else if(A[1] == B[1]){
            return A[2] < B[2];
        }
    }
    return false;
}

 

정렬한 result 벡터를 이용하여 장르별로 최대 2개의 노래를 answer에 저장하여 답을 구해주었다.

 

---

풀이 코드 - C++

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

bool cmp(const vector<int> &A, const vector<int> &B){    
    if(A[0] > B[0])
        return true;
    else if (A[0] == B[0]){
        if(A[1] > B[1])
            return true;
        else if(A[1] == B[1]){
            return A[2] < B[2];
        }
    }
    return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    // 장르별 총 재생 수 구하기
    int len = plays.size();
    unordered_map<string, int> dic;
    for(int i = 0; i < len; i++){
        dic[genres[i]] += plays[i];
    }
    
    // 장르별 총 재생 수, 노래 재생 수, 노래 고유 번호 저장
    vector<vector<int>> result(len, vector<int>(3));
    for(int i = 0; i < len; i++){
        result[i][0] = dic[genres[i]];
        result[i][1] = plays[i];
        result[i][2] = i;
    }
    
    // 장르별로 최대 2개 저장
    sort(result.begin(), result.end(), cmp);
    vector<int> answer;
    int count = 0;
    int now = result[0][0];
    for(int i = 0; i < len; i++){
        if(now != result[i][0]){
            count = 0;
            now = result[i][0];
        }
        if(count == 2)
            continue;
        answer.push_back(result[i][2]);
        count++;
    }
    return answer;
}

실행 결과

실행 결과 : 통과 (100.0)