코딩테스트 -- 베스트앨범 - (프로그래머스 / C++)

프로그래머스

 

 

문제!

---

 

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

               genres                                                                                         plays                                               return

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

 

---

요약하면 

1. 속한 노래가 많이 재생된 장르를 먼저 수록
2. 장르 내에서 많이 재생된 노래를 먼저 수록
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록

순서대로 기준을 지켜가며 각 장르당 2개씩 음악을 선택, 인덱스를 출력하라는 문제입니다

 

음...

일단 기준이 장르총 재생수 , 곡 재생수, 인덱스 이렇게 3가지로 나뉘어져있으니 

 

저는 하나로 묶어보겠습니다.

 

3개를 한그룹으로... tuple을 사용해보겠습니다.

 

시작!

tuple을 사용하기전 장르별 총 재생수를 map을 통해 구해줍시다.

for문 한번으로 모든곡을 돌아다니며 재생수를 추가!

map <string , int> genres_hash;
    
    for(int i=0;i<genres.size();i++){
        if (genres_hash.find(genres[i]) != genres_hash.end()){
            genres_hash[genres[i]]+=plays[i];
        }
        else{
            genres_hash[genres[i]]=plays[i];
        }
    }

 

그다음 tuple을 만들어 주고 각각의 값들을 넣어줍시다.

vector<tuple <int, int, int >> music_list;// 장르총 재생수 , 곡 재생수, 인덱스
    
    for(int i=0;i<genres.size();i++){
        music_list.push_back(make_tuple(genres_hash[genres[i]],plays[i],i));
    }

 

이제 정렬을 해야하는데

아래처럼 sort_music이라는 bool형 함수로 어떻게 정렬될지 정해줍시다! (중요)

sort(music_list.begin(), music_list.end(),sort_music);

 

함수는 아래처럼 구성할수있습니다.

bool sort_music(const tuple<int,int,int>& a, const tuple<int,int,int>& b){// 장르총 재생수 , 곡 재생수, 인덱스
    if(get<0>(a) == get<0>(b)){//장르 재생수가 같으면
        if(get<1>(a) == get<1>(b)){//곡별 재생수가 같으면
            return get<2>(a) < get<2>(b);//인덱스 비교
        }
        else {
            return get<1>(a) > get<1>(b);//재생수 비교
        }     
    }
    else{
        return get<0>(a) > get<0>(b);//장르별 재생수 비교
    }
    
}

return으로 a,b간의 크기비교를 해주는 것으로 sort를 할수있습니다.

a > b -- 내림차순

a < b -- 오름차순

 

여기까지 하면 모든 기준에 따라 tuple 벡터가 정렬이 되었습니다!

 

 

 

이제 2개씩 선출하여 answer에 넣어주겠습니다.

    int memo_num=0;//수 저장
    bool two_music=true;// 2개이상인지
    
    for(int i=0;i<genres.size();i++){
        if(memo_num==get<0>(music_list[i])){//같다?
            if(two_music){//두번째같을때까지는 저장
                answer.push_back(get<2>(music_list[i]));
            }
            two_music=false;//세번째부터는 안됨
        }
        else{// 첫번째볼때는 여기서 저장 및 초기화
            two_music=true;
            memo_num=get<0>(music_list[i]);
            answer.push_back(get<2>(music_list[i]));
        }
    }

이부분이 좀 설명하기 그런데 한번 위에서부터 차근차근 내려오시면 이해하실수 있을겁니다!

 

여기까지가 끝!

 

ALL

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

#include<algorithm>
using namespace std;

bool sort_music(const tuple<int,int,int>& a, const tuple<int,int,int>& b){// 장르총 재생수 , 곡 재생수, 인덱스
    if(get<0>(a) == get<0>(b)){
        if(get<1>(a) == get<1>(b)){
            return get<2>(a) < get<2>(b);
        }
        else {
            return get<1>(a) > get<1>(b);
        }     
    }
    else{
        return get<0>(a) > get<0>(b);
    }
    
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map <string , int> genres_hash;
    
    for(int i=0;i<genres.size();i++){
        if (genres_hash.find(genres[i]) != genres_hash.end()){
            genres_hash[genres[i]]+=plays[i];
        }
        else{
            genres_hash[genres[i]]=plays[i];
        }
    }
    
    vector<tuple <int, int, int >> music_list;// 장르총 재생수 , 곡 재생수, 인덱스
    
    for(int i=0;i<genres.size();i++){
        music_list.push_back(make_tuple(genres_hash[genres[i]],plays[i],i));
    }
    
    sort(music_list.begin(), music_list.end(),sort_music);

    int memo_num=0;
    bool two_music=true;
    for(int i=0;i<genres.size();i++){
        if(memo_num==get<0>(music_list[i])){
            if(two_music){
                answer.push_back(get<2>(music_list[i]));
            }
            two_music=false;
        }
        else{
            two_music=true;
            memo_num=get<0>(music_list[i]);
            answer.push_back(get<2>(music_list[i]));
        }
    }

    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!