베스트앨범

https://programmers.co.kr/learn/courses/30/lessons/42579

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <tuple>
#include <algorithm>
#include <functional>
#include <iostream>
#include <set>

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays)
{
  vector<int> answer;
  //genre, set<playCount, songID>
  //set will sort songs largest to smallest
  std::unordered_map<string, std::set<std::tuple<int, int>>> genre_playsOrder;
  //genre, total count
  std::unordered_map<string, int> genreCount;
  //total count, genre
  //to find the order of genre
  std::vector<std::tuple<int, string>> totalOrder;
  for (int i = 0; i < genres.size(); ++i)
  {
    genreCount[genres[i]] += plays[i];
    auto &playCountIDSet = genre_playsOrder[genres[i]];
    //add negation to sort largest play times to smallest
    playCountIDSet.emplace(-plays[i], i);
  }

  //to find the genre that has largest playtimes
  for (const auto &genre : genreCount)
  {
    totalOrder.emplace_back(std::get<1>(genre), std::get<0>(genre));
  }
  std::sort(totalOrder.begin(), totalOrder.end(),
            [](const std::tuple<int, string> &a, const std::tuple<int, string> &b) {
              return std::get<0>(a) > std::get<0>(b);
            });

  for (const auto &count_genre : totalOrder)
  {
    auto &genreName = std::get<1>(count_genre);
    auto &playCountIdSet = genre_playsOrder[genreName];
    int count = 0;
    for (const auto &plays_id : playCountIdSet)
    {
      ++count;
      answer.emplace_back(std::get<1>(plays_id));
      if (count >= 2)
      {
        break;
      }
    }
  }
  return answer;
}

이 문제는 프로그래머스 코테연습 해시 에 있는 level3 문제로 사실 알고리즘적으로 어려운 문제이기보단 구현하는데 복잡했던 문제같다. 일단 어떤 장르가 가장많은지 알기위해 unordered_map<장르이름, 그장르횟수> 만들었고, 어떤장르에 속하는 노래들을 많이 재생된 횟수로 정렬하기위해 unordered_map<장르이름, set<tuple<노래횟수, 노래ID>>> 를 만들었다. 원래는 set이 아닌 multimap을 썼었는데 문제가 multimap이 key 기준으로는 정렬을해도 value들은 그냥 들어온대로 되서 노래들의 id들이 오름차순으로 정렬이 안되어서 tuple의 set으로 바꾸었다. multipmap쓰기 싫었는데 잘됬지뭐..

그다음엔 루프 한바퀴돌아서 필요한 정보들은 다 넣어주고난뒤(각노래의 재생횟수를 내림차순으로 정렬하기위해 음수화 시켜 set에 넣어주었다) genreCount 을 순회하여 vector<tuple<횟수, 장르>>에 넣어준뒤 그 vector를 횟수기준 내림차순으로 정렬해주었다. 그래야 어떤 장르가 많이 재생되었는지 알 수 있으므로.

마지막으론 totalOrder vector를 돌며 많이 재생된 장르의 이름으로 genre_playsOrder map에서 검색한 후 set의 맨앞 두개를 뽑아 거기에 들어있던 노래의 id를 answer에 차곡차곡 넣어주면 끝.