프로그래머스 42579 - 베스트앨범 (c++)

프로그래머스 42579 - 베스트앨범

문제 링크

생각 및 접근

• 시간이 꽤 걸린 문제였고, 새롭게 알게 된 C++ 지식들이 많았다.
• 선언한 자료 구조
  • 음악 장르 별로 음악 재생 수의 합을 구해서 내림차순으로 정리하기 위한 map<string, int> sumGenre; vector<pair<string, int>> v;
  • 음악 장르 별로 음악을 저장하고, 음악의 index 번호와 재생 수를 저장하는 map<string, vector<Music>> groupByGenre;
  • 음악의 index 번호와 재생 수를 한꺼번에 저장하고, operator 함수를 선언하기 위해 선언한 객체 struct Music{};

새로 배운 내용은 볼드 처리 하였습니다.

• 기

  • struct Music

      struct Music{
          int index;
          int play;
          Music(int b, int c){
              index = b;
              play = c;
          }
          bool operator < (const Music & b) const {
              if(play == b.play){
                  return index < b.index;
              }
              return play > b.play;
          }
      };

  • sumGenre와 groupByGenre에 값을 채워넣는다.

      for(int i = 0; i < numMusic; i++){
          sumGenre[genres[i]] += plays[i];
          groupByGenre[genres[i]].push_back(Music(i, plays[i]));
      }

• 승

  • map을 vector로 변환하기
    • vector로 변환하고, sum이 큰 순서대로 sort한다.

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

      vector<pair<string, int>> v;
      for(auto & k : sumGenre){
        v.push_back(make_pair(k.first, k.second));
      }
      sort(v.begin(), v.end(), cmp);

• 전, 결

  • vector v를 순회하면서, groupByGenre의 value인 vector를 sort한다.

      for(int i = 0; i < v.size(); i++){
          string target = v[i].first;
          sort(groupByGenre[target].begin(), groupByGenre[target].end());

    • sort의 방식은 play 오름차순, play 수가 같다면 index 내림차순으로 정렬한다.

  • 정렬 이후, 장르의 음악 수에 따라서 2개를 넣을 지, 1개를 넣을 지 판단한다.

          for(int i = 0; i < min(2, (int) groupByGenre[target].size()); i++){
              answer.push_back(groupByGenre[target][i].index);
          }
      }
    
      return answer;
    

코드

#include <bits/stdc++.h>
using namespace std;

struct Music{
    int index;
    int play;
    Music(int b, int c){
        index = b;
        play = c;
    }
    bool operator < (const Music & b) const {
        if(play == b.play){
            return index < b.index;
        }
        return play > b.play;
    }
};

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

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

    int numMusic = genres.size();

    map<string, int> sumGenre;
    map<string, vector<Music>> groupByGenre;

    for(int i = 0; i < numMusic; i++){
        sumGenre[genres[i]] += plays[i];
        groupByGenre[genres[i]].push_back(Music(i, plays[i]));
    }

    vector<pair<string, int>> v;
    for(auto & k : sumGenre){
        v.push_back(make_pair(k.first, k.second));
    }
    sort(v.begin(), v.end(), cmp);

    for(int i = 0; i < v.size(); i++){
        string target = v[i].first;
        sort(groupByGenre[target].begin(), groupByGenre[target].end());

        for(int i = 0; i < min(2, (int) groupByGenre[target].size()); i++){
            answer.push_back(groupByGenre[target][i].index);
        }
    }

    return answer;
}

채점 결과