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

적절한 자료구조를 선택해서 사용하는지 보기 위한 문제 같다. 어렵게 생각하지 않고 시키는 대로 건실하게 코딩하기만 하면 된다.

입출력 예를 보면 genres(key)가 주어지고 그에 따른 plays(value)가 주어지기 때문에 크게 고민하지 않고 std::map 컨테이너를 다음과 같이 이용했다.

1. map<string, int> genre
   • 장르당 총 몇번 재생되었는지 저장하는 데이터이다.
   • map[장르]에 plays[i]를 계속 더해준다.
2. map<string, vector<pair<int, int>>> songs
   • 각각의 곡을 장르별로 모아둔 데이터이다.
   • 곡의 정보 {인덱스, 재생횟수}를 map[장르]에 배열로 가지고 있는다.
   • songs의 value를 std::vector로 선언한 데에는 이유가 있는데, 수록곡의 우선순위가 "재생횟수"와 "인덱스"에 따라 정해지기 때문에 장르에 속한 곡들을 이러한 순서로 정렬해줄 필요가 있어서다.

아래는 작성한 코드이다.

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

using namespace std;

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

vector<int> solution(vector<string> genres, vector<int> plays)
{
    map<string, int> genre;
    map<string, vector<pair<int, int>>> songs; // genre, index, plays

    // 데이터 초기화
    for (int i = 0; i < genres.size(); ++i)
    {
        genre[genres[i]] += plays[i];
        songs[genres[i]].push_back({i, plays[i]});
    }
    
    // 장르별로 곡들을 정렬
    for (auto &e : songs)
        sort(e.second.begin(), e.second.end(), cmp);
    
    vector<int> ans;
    
    while (!genre.empty())
    {
        // 재생횟수가 높은 장르를 선정
        string selected;
        int M = 0;
        for (auto e : genre)
        {
            if (e.second > M)
            {
                M = e.second;
                selected = e.first;
            }
        }
        
        // 선택된 장르에서 재생횟수가 많고, 인덱스가 낮은 곡을 우선적으로 선정
        for (int i = 0; i < songs[selected].size() && i < 2; ++i)
            ans.push_back(songs[selected][i].first);
        
        // 선택한 장르에 대한 작업이 끝났다면 지우기
        genre.erase(selected);
    }
    
    return ans;
}

---

주의사항

// 장르별로 곡들을 정렬
for (auto &e : songs)
	sort(e.second.begin(), e.second.end(), cmp);

이 부분은 포인터나 깊은 복사와 얕은 복사에 대한 개념이 익숙하지 않다면 헷갈릴 수 있다.

auto &e를 참조자(레퍼런스)로 받지 않고 auto e로 받아버리면 songs 안에 있는 데이터를 정렬하는 것이 아니라, songs의 데이터를 복사하고 복사한 데이터를 정렬하는 것이다.

우리는 for문을 벗어나서도 정렬된 songs의 데이터를 이용하고 싶기 때문에 songs의 주소값을 참조해서 해당 데이터를 직접 정렬해야 하는 것이다.