[3] 베스트 앨범

참고 사이트 : 알고리즘(C++) / 프로그래머스 level 3 : 베스트앨범 (tistory.com)

 

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <list>

using namespace std;

using StringPair = pair<string, int>;
using IntPair = pair<int, int>;

// 내림차순 정렬
bool CmpStr(StringPair& a, StringPair& b)
{
    return a.second > b.second;
}

bool CmpInt(IntPair& a, IntPair& b)
{
    return (a.first == b.first) ? a.second < b.second : a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays)
{
    vector<int> answer;
    unordered_map<string, int> mapScore;

    // 초기화
    for (int i = 0; i < genres.size(); i++)
        mapScore[genres[i]] += plays[i];

    // 재생 값 기준 정렬
    vector<StringPair> vMostPlayed(mapScore.begin(), mapScore.end());
    sort(vMostPlayed.begin(), vMostPlayed.end(), CmpStr);

    for (int i = 0; i < vMostPlayed.size(); i++)
    {
        vector<IntPair> genre;

        for (int j = 0; j < plays.size(); j++)
        {
            if (vMostPlayed[i].first == genres[j])
                genre.push_back({plays[j],j});
        }
        sort(genre.begin(), genre.end(), CmpInt);

        answer.push_back(genre[0].second);

        if (genre.size() >= 2)
            answer.push_back(genre[1].second);
    }
    return answer;
}

 

틀린 코드

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

using namespace std;

using StringPair = pair<string, int>;

#define y first
#define x second

struct sMusic
{
    string genre = "";
    int play = 0, idx = 0;

public:
    bool operator==(const sMusic& Ref) const
    {
        return this->genre == Ref.genre &&
               this->play == Ref.play &&
               this->idx == Ref.idx;
    }

    bool operator!=(const sMusic& Ref) const
    {
        return !(*this == Ref);
    }
};

// 오름차순 정렬
bool Cmp(sMusic music1, sMusic music2)
{
    return music1.play > music2.play;
}

vector<int> solution(vector<string> genres, vector<int> plays)
{
    vector<int> answer;
    map<string, int> mapCount;
    list<sMusic> lMusic;

    for (int i = 0; i < genres.size(); i++)
    {
        lMusic.push_back({ genres[i], plays[i], i });
        mapCount[genres[i]] = 0;
    }
    lMusic.sort(Cmp);
    string tmp;

    while(answer.size() < 4)
    {
        sMusic music = (tmp != "") ? *find_if(lMusic.begin(), lMusic.end(), [&](const sMusic& lVal) {return lVal.genre == tmp; }) : lMusic.front();        
        auto genre = music.genre;
        auto idx = music.idx;

        if (mapCount[genre] == 0)
        {
            mapCount[genre]++;
            answer.push_back(idx);
            lMusic.pop_front();
            tmp = genre;
        }
        else
        {
            mapCount[genre]++;
            answer.push_back(idx);
            lMusic.remove(music);
            tmp = "";
        }
    }
    return answer;
}