[C++]베스트 앨범

장르 이름 및, 장르에 속한 곡들의 재생수의 합으로 간단하게 맵을 만들어도 될 것 같다.
여기서는 정렬을 해야하니까 해시보다는 맵이 잘 어울리리라 생각했다.
Index를 또 참고하기 싫어서 넣는김에 인덱스 값도 문자열로 변환해서 더해줬다.

    map<string,playsInf> genresMap;
    for(int i = 0; i < genres.size(); i++) {
        genresMap[genres[i]].first+=plays[i];
        genresMap[genres[i]].second += to_string(i);
    }

genre name : classic
genre playtime : 1450
genre index : 023

genre name : pop
genre playtime : 3100
genre index : 14
출력하면 이런 순서로 출력된다. 맵은 자동정렬되나 그 기본값은 키 값을 오름차순으로 정렬하기 때문에, 이름이 사전오름차순으로 'c'lassic -> 'p'op으로 정렬된 것!
나는 밸류값을 내림차순으로 배열해야 한다! 찾아보니, 벡터로 옮겨서 sort를 해야한다고 한다.

    bool cmp(pair<string,playsInf>& a, pair<string,playsInf>& b) {
    return a.second.first > b.second.first;
}
    
    vector<pair<string,playsInf>> genresVector(genresMap.begin(),genresMap.end());
    sort(genresVector.begin(), genresVector.end(),cmp);

genre name : pop
genre playtime : 3100
genre index : 14

genre name : classic
genre playtime : 1450
genre index : 023
이렇게, 플레이타임 내림차순(3100 > 1450) 으로 배열된다. 제한 사항에서 무조건 장르의 재생시간의 합은 다르다고 명시했기 때문에 더 고려할 사항은 없음
근데 이럴거면 맵을 쓰는 이유가..? 벡터..정렬하는데.. 맵을 쓸 이유가? 있나...
하긴 이럴거면 맵쓸게아니라 해시쓰는게 맞는 것 같다. 맵의 기본 정렬기능을 안쓰기 때문에 정렬낭비니까...

이제 장르별로 내림차순정렬해서 두 곡을 뽑을 차례이다.
이를 위해, 장르마다 pair(index,playtime) 형태로 저장할 벡터를 생성하고 모두 넣어준다.
Pop 장르의 경우, [[1,600],[4,2500]] 으로 저장되고 Classic 장르의 경우 [[0,500],[2,150],[3,800]] 으로 저장함.

        for(int i = 0; i < ele.second.second.size(); i++) {
            //pair(index,playtime) sortedPlays
            int index = ele.second.second[i]-'0';
            sortedPlays.emplace_back(index,plays[index]);
        }

정렬에는 조건이 있다.
1. 내림차순
2. 같은 값이라면 고유번호 작은순으로 정렬
3. 최대 2개만 필요하다.(다 정렬할 필요가 없다.)

bool partialCmp(pair<int,int>& a, pair<int,int>& b) {
    if(a.second == b.second) {  //if same
        return a.first < b.first;
    }
    return a.second > b.second;
}

이런 조건에 따라 일단 정렬함수는 이렇게 짰다. 1,2번이 고려되어있다.

        if(sortedPlays.size() > 1) {
            partial_sort(sortedPlays.begin(),sortedPlays.begin()+2,sortedPlays.end(),partialCmp);   //sort just 2 element 
        }
        
        for(int j = 0; j < 2; j++) {
            answer.push_back(sortedPlays[j].first);
            if(sortedPlays.size() == 1)
                break;
        }

3번을 고려해서 정렬하고, 출력한다. 이후 해당 벡터를 클리어해준다.

다만 채점하니 5,6,7,8,10,12,13,14번이 틀린다. ㅜㅜ 정확도 46.7 ...
질문하기에 올라와있는 총 15페이지의 반례와 설명을 찾아봐도 다 충족하고, 예외사항도 다 충족한 상황이라 어리벙벙...
으아악

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

using namespace std;
typedef pair<int,string> playsInf;  //int is playsvalue, string is index

bool cmp(pair<string,playsInf>& a, pair<string,playsInf>& b) {
    return a.second.first > b.second.first;
}

bool partialCmp(pair<int,int>& a, pair<int,int>& b) {
    if(a.second == b.second) {  //if same
        return a.first < b.first? true : false;
    }
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    map<string,playsInf> genresMap;
    vector<pair<int,int>> sortedPlays;
    vector<int> answer;
    
    for(int i = 0; i < genres.size(); i++) {
        genresMap[genres[i]].first+=plays[i];
        genresMap[genres[i]].second += to_string(i);
    }
    vector<pair<string,playsInf>> genresVector(genresMap.begin(),genresMap.end());
    sort(genresVector.begin(), genresVector.end(),cmp);
    
    for(auto ele : genresVector) {  //for every genre
        cout << ele.first<< ele.second.first << endl;
        for(int i = 0; i < ele.second.second.size(); i++) {
            //pair(index,playtime) sortedPlays
            int index = ele.second.second[i]-'0';
            sortedPlays.emplace_back(index,plays[index]);
        }
        //sort
        if(sortedPlays.size() > 1) {
            partial_sort(sortedPlays.begin(),sortedPlays.begin()+2,sortedPlays.end(),partialCmp);   //sort just 2 element 
        }
        
        for(int j = 0; j < 2; j++) {
            answer.push_back(sortedPlays[j].first);
            cout << "answer << " << sortedPlays[j].first<< "/" << sortedPlays[j].second << endl;
            if(sortedPlays.size() == 1)
                break;
        }
        sortedPlays.clear();
    }

    
    return answer;
}

전체 코드는 이렇다 ㅜㅜ

장르개수제한없음, 한곡만담을때, 재생횟수같을때 등등 다 고려했는데 뭐가 문젠걸까?(물론 고려 못했으니까 틀리는거겠지만)

다른사람의 풀이

결국 내 풀이로 문제를 풀지 못하고 다른 사람 풀이를 봐야했다;
다른사람 풀이로 풀면 내 코드에서 무엇이 누락되었는지 알테니까?
https://velog.io/@gowoonsori/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4cpp%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94
이분의 코드를 참조함
내가 굳이 문자열 형태로 index를 모두 적은게 map으로 이중벡터? 형태가 불가능할거라고 생각해서였는데 저렇게 선언해도 되는구나.
Unordered_map<string,vector<pair<int,int>>> 로 하고 저장하면 예시의 경우
['classic', [(500,0),(150,2),(800,3)], ['pop', [(600,1),(2500,4)] 이렇게 저장하는거임
여기서 second 반복문에서 first값을 정렬하는거임.

근데 이래도 내가 쓴 방식이 세련되지 못했을 뿐이고 빼트린게 없는거같음.....;;;
일단 이 문제는 일주일 정도 후에 다시 풀어보기로.