프로그래머스

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

스누징어 2023. 6. 3. 14:35

베스트 앨범

내가 만든 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

struct SongInfo{
    string genre;
    int play;
    int index;
};

bool compare(const SongInfo& s1, const SongInfo& s2){
    if(s1.genre == s2.genre){
        if(s1.play == s2.play){
            return s1.index < s2.index;
        }
        else{
            return s1.play > s2.play;
        }
    }
    else{
        return s1.genre > s2.genre;
    }
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> maps;
    multimap<int, string> mm;
    
    for(int i = 0; i < genres.size(); i++){
        maps[genres[i]] += plays[i];
    }
    
    auto iter = maps.begin();
    while(iter != maps.end()){
        mm.insert(pair<int, string>(iter->second, iter->first));
        iter ++;
    }
    
    vector<SongInfo> songInfo;
    for(int i = 0; i < genres.size(); i++){
        SongInfo a = { genres[i], plays[i], i};
        songInfo.push_back(a);
    }
    
    sort(songInfo.begin(), songInfo.end(), compare);
    
    auto mm_iter = mm.rbegin();
    int i = 0;
    while(mm_iter != mm.rend()){
        for(i = 0; i < songInfo.size(); i++){
            if(songInfo[i].genre == mm_iter->second){
                break;
            }
        }
        answer.push_back(songInfo[i].index);
        if(songInfo[i].genre == songInfo[i+1].genre)
            answer.push_back(songInfo[i+1].index);
        
        mm_iter++;
    }
    
    
    return answer;
}

* 처음으로 푼 3 레벨 문제...

  풀었다는 거에 의미를 가지자

 

 

코드 설명

* 생각 해야할 문제점 3가지

 

1. 각 장르의 총 재생 수로 정렬한다.

>> map<string, int>를 <장르, 총 재생 수>로 만들어서 재생 수를 모두 더한다.

    "총 재생 수"로 정렬해야 하기 때문에 map<int, string>을 다시 만들어서 집어넣는다.

    이때 "총 재생 수"는 중복 가능이므로 multimap으로 구현한다.

    (multimap을 사용해 알아서 정렬)

 

2. 장르, 재생 수, index라는 데이터들이 연계되어야 한다.

>> SongInfo라는 구조체를 만들어서 사용

 

3. 장르를 총 재생 수로 정렬하고, 각 장르 별로 재생 수로 정렬한다.

>> 비교 함수를 직접 만들어 <algorithm>의 sort() 함수에 적용한다.

 

 

예상하지 못한 문제점

1. sort() 함수에 넣을 compare() 함수를 만들었는데,

    비교하려면 장르에 최소 2개 이상이 들어있어야 한다는 가정이 있어야 한다.

>> 장르에 1개밖에 없으면 에러가 나는 문제를 해결해야 한다.

     (비교를 하려면 최소 2개 이상이라는 조건이 충복되는지 확인하자!)

 

 

본받을 만한 코드 - 1

* 구조체를 따로 만들지 않고 unorderd_map<string, vector<pair<int, int>>>를 사용하는 방법

>> 솔직히 이거 다루는 게 더 어지러운 거 같음...

     하지만 할 수 있다는 게 놀랍다.

     map[key].push_back(make_pair(int, int)); 형식으로 삽입한다.

    vector<pair<int, int>> vec = map[key]; 로 반환해서 사용한다.

>> 굳이 unorderd_map을 사용하는 이유가 정렬 함수를 따로 만들어서 사용하려고 그런 거 같다.

 

 

본받을 만한 코드 - 2

* 구조체를 따로 만들지 않고 map<string, map<int, vector<int>>>를 사용하는 방법

>> vector<int>를 사용하는 이유가 중복 재생 수를 가지는 index를 넣기 때문에

 

 

 

 

 

 

 

 

반응형