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

문제

문제 링크 - 베스트앨범

문제는 이미 숙지한 사람들만 들어왔을 것이라 생각하므로 굳이 다시 설명하지 않음

풀이

알고리즘

• map에 장르명, 고유번호, 재생횟수를 저장할 수 있는 구조 필요
• 장르별로 노래 재생횟수를 모두 더한 것이 큰 순으로 정렬
• 장르 내에 재생횟수가 같은 노래는 plays 배열의 인덱스가 낮은 순으로 정렬
• 장르 내에 곡은 재생횟수가 많은 2곡까지만, 1곡만 있는 경우도 생각해야 함
• unordered_map<string, vector> album 구조
  

코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Songs
{
public:
    int num;
    int plays;

    Songs(int plays, int num)
    {
        this->num = num;
        this->plays = plays;
    }
};

bool cmp(Songs a, Songs b)
{
    if (a.plays == b.plays)
        return a.num < b.num;
    else
        return a.plays > b.plays;
}

bool cmp2(pair<int, unordered_map<string, vector<Songs>>::iterator> &a,
          pair<int, unordered_map<string, vector<Songs>>::iterator> &b)
{
    return a.first > b.first;
}

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

    unordered_map<string, vector<Songs>> album;

    for (int i = 0; i < genres.size(); i++)
        album[genres[i]].push_back(Songs(plays[i], i));

    for (auto iter = album.begin(); iter != album.end(); iter++)
        sort((*iter).second.begin(), (*iter).second.end(), cmp);

    vector<pair<int, unordered_map<string, vector<Songs>>::iterator>> order_v;
    for (auto iter = album.begin(); iter != album.end(); iter++)
    {
        auto songs_vec = (*iter).second;
        int plays_sum = 0;
        for (int i = 0; i < songs_vec.size(); i++)
            plays_sum += songs_vec[i].plays;

        order_v.push_back(make_pair(plays_sum, iter));
    }

    sort(order_v.begin(), order_v.end(), cmp2);

    for (int i = 0; i < order_v.size(); i++)
    {
        for (int j = 0; j < (*order_v[i].second).second.size(); j++)
        {
            if (j == 2)
                break;
            answer.push_back((*order_v[i].second).second[j].num);
        }
    }

    return answer;
}

코드. 근데 이제 주석을 첨가한...

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

using namespace std;

// map의 second 값: vector<Songs>
// Songs(고유번호, 재생횟수)
// pair로 가능하지만 객체로 만들어 접근하는 편이 더 직관적임
class Songs
{
public:
    int num;   // 고유번호
    int plays; // 재생횟수

    Songs(int plays, int num)
    {
        this->num = num;
        this->plays = plays;
    }
};

// vector<Songs> 정렬: 내림차순
// 장르별 재생횟수가 많은 2 곡까지만 뽑아주기 위함
// 재생횟수가 같으면 고유번호가 낮은 순, 그 외에는 재생횟수가 많은 순
bool cmp(Songs &a, Songs &b)
{
    if (a.plays == b.plays)
        return a.num < b.num;
    else
        return a.plays > b.plays;
}

// order_v 정렬: 장르별 재생횟수 합의 내림차순
// 장르별로 재생횟수의 합이 큰 순으로 정렬하기 위함
bool cmp2(pair<int, unordered_map<string, vector<Songs>>::iterator> &a,
          pair<int, unordered_map<string, vector<Songs>>::iterator> &b)
{
    return a.first > b.first;
}

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

    //map을 굳이 사용할 이유가 없기 때문에 더 빠른 탐색이 가능한 unordered_map 사용
    //album[장르명, [고유번호, 장르별 재생횟수]]
    unordered_map<string, vector<Songs>> album;

    //genres 벡터에서 재생횟수와 고유번호를 찾아 album에 넣어줌
    for (int i = 0; i < genres.size(); i++)
        album[genres[i]].push_back(Songs(plays[i], i));

    //album의 장르 갯수만큼 돌면서 장르별 vector<Songs> 을 내림차순 정렬
    for (auto iter = album.begin(); iter != album.end(); iter++)
        sort((*iter).second.begin(), (*iter).second.end(), cmp);

    //정렬 후 album 원소 테스트 출력
    cout << "<sorted>" << endl;
    for (auto iter = album.begin(); iter != album.end(); iter++)
    {
        cout << "[" << (*iter).first << "]" << endl;
        for (int i = 0; i < (*iter).second.size(); i++)
        {
            cout << "num: " << (*iter).second[i].num << "\t// ";
            cout << "plays: " << (*iter).second[i].plays;
            cout << endl;
        }
        cout << endl;
    }

    // order_v[장르별 재생횟수 합, 장르별 반복자]
    vector<pair<int, unordered_map<string, vector<Songs>>::iterator>> order_v;
    for (auto iter = album.begin(); iter != album.end(); iter++)
    {
        //songs_vec == vector<Songs>
        auto songs_vec = (*iter).second;
        int plays_sum = 0;
        for (int i = 0; i < songs_vec.size(); i++)
            plays_sum += songs_vec[i].plays;

        order_v.push_back(make_pair(plays_sum, iter));
    }

    //order_v의 장르별 재생횟수를 기준으로 내림차순 정렬
    sort(order_v.begin(), order_v.end(), cmp2);

    //정렬 후 order_v 원소 테스트 출력
    cout << "<sorted_order_v>" << endl;
    for (int i = 0; i < order_v.size(); i++)
    {
        cout << "i: " << i << " // " << order_v[i].first << endl;
    }
    cout << endl;

    //order_v[i].second == album의 iterator
    //(*order_v[i].second).second[j] == vector<Songs>
    //answer 벡터에 장르별로 최대 2곡까지만 넣어줌
    for (int i = 0; i < order_v.size(); i++)
    {
        for (int j = 0; j < (*order_v[i].second).second.size(); j++)
        {
            //장르별 곡 갯수는 최대 2개까지만
            if (j == 2)
                break;

            //고유번호를 넣어줌
            answer.push_back((*order_v[i].second).second[j].num);
        }
    }

    return answer;
}

//테스트 케이스 출력
int main()
{
    vector<string> genres1 = {"classic", "pop", "classic", "classic", "pop"};
    vector<int> plays1 = {500, 600, 150, 800, 2500};

    vector<string> genres2 = {"classic", "pop", "classic", "classic", "pop", "rap", "kpop", "kpop"};
    vector<int> plays2 = {500, 600, 150, 800, 2500, 50, 3000, 10};

    vector<string> genres3 = {"classic", "pop", "pop"};
    vector<int> plays3 = {500, 600, 650};

    vector<int> answer = solution(genres1, plays1);

    cout << "answer: ";
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << ", ";
    }
    cout << endl;
}

주석 코드 출력 결과

<sorted>
[pop]
num: 4  // plays: 2500
num: 1  // plays: 600

[classic]
num: 3  // plays: 800
num: 0  // plays: 500
num: 2  // plays: 150

<sorted_order_v>
i: 0 // 3100
i: 1 // 1450

answer: 4, 1, 3, 0,

여담

프로그래머스 레벨 3단계는 처음 풀어본 문제였는데 확실히 레벨 3에 걸맞은 난해한 문제였다.
어느 부분이 난해하냐면 로직을 생각하는 건 30분 정도 걸렸는데, 사실 그것보다는 실제로 코드를 작성함에 있어서 어려움을 많이 느꼈다. 대충 로직 짜는 것의 10배 정도 걸린 듯.

map을 통해서 노드 하나를 [장르명, [고유번호, 재생횟수]]의 구조로 만듦에 있어서 map<string, map<int, int>>부터 생각했지만 입력값을 탐색하며 계속 값을 넣어주어야 하고, 원소들에 접근해서 정렬 등 구구절절 가공을 해주어야 함에 있어서 map<int, int>은 별로 메리트를 못 느꼈다.
pair, tuple 등 별걸 다 해보다가 객체를 만들어준 후 vector로 만드는 것이 가장 직관적이고 접근도 용이하게 느껴졌다.

마지막으로 vector<pair<int, unordered_map<string, vector>::iterator>> order_v; 이 구조 자체는 마음에 들게 잘 만든 것 같은데, iterator까지 타이핑이 너무 길어져서 좀 열 받긴 한다.