[C++] 프로그래머스 - 베스트 앨범 (해시), sorting

이번 포스팅에서는 프로그래머스 코딩 테스트 중 해시 베스트 앨범에 대한 글입니다. 최근 C++을 공부하고 있는데 STL 라이브러리들을 사용하는 방식이 다소 생소하게 느껴지네요. 그간 python에서 얼마나 편하게 여러 기능들을 제공했었는지 새삼 깨닫고 있습니다.

---

문제 정의 (프로그래머스 사이트 발췌)

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

---

["classic", "pop", "classic", "classic", "pop"] [500, 600, 150, 800, 2500] [4, 1, 3, 0]
입출력 예 설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

고유 번호 3: 800회 재생
고유 번호 0: 500회 재생
고유 번호 2: 150회 재생
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

고유 번호 4: 2,500회 재생
고유 번호 1: 600회 재생
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

---

대충 이런 과제이고, 다양한 접근법이 있겠지만 아무리해봐도 시간 복잡도가 O(n^{2})으로 나왔지만 다행히 모든 테스트는 통과했습니다. 제가 접근한 방식은 다음과 같습니다.

---

• Hash 를 이용해서 장르별로 재생 시간을 모두 합산 → 장르 순서를 먼저 정합니다.
• sorting을 활용, 장르별로 재생 시간이 긴 index들을 추출하여 answer에 emplace_back 해줍니다.

---

단순하지만, c++을 처음해보는 저로써는 상당히 애 좀 먹었습니다. 이 과정에서 필요했던 Sorting을 정리해보면 다음과 같습니다.

---

Sorting

sorting을 하기 위해서는 먼저 Hash 에서 vector로 변환해주어야 합니다.

---

    
    unordered_map<string,int> finder;
    // 가장 많이 재생된 장르 찾기 (unordered_map)
    for (int i=0; i<genres.size(); i++) {
        finder[genres[i]] += plays[i];
    }
    
    // unordered_map 을 vector로 변환하여 sorting 하기
    vector<pair<string, int> > arr;
    for (const auto &item : finder) {
        arr.emplace_back(item);
    }
    
    // 벡터 값의 두번째에 해당하는 play의 합산 시간을 기준으로 정렬
    std::sort(arr.begin(), arr.end(), [] (auto x, auto y) {return x.second > y.second;});
    
  

___ 먼저 vector에는 `(key, value)` 형태로 변환하게 되고, vector에서 first나 second type의 크기에 따라 정렬하게 되는 방식입니다. ___ 전체 코드는 다음과 같습니다. ___

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <iostream>
 
 
using namespace std;
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    unordered_map<string,int> finder;
    // 가장 많이 재생된 장르 찾기 (unordered_map)
    for (int i=0; i<genres.size(); i++) {
        finder[genres[i]] += plays[i];
    }
    
    // unordered_map 을 vector로 변환하여 sorting 하기
    vector<pair<string, int> > arr;
    for (const auto &item : finder) {
        arr.emplace_back(item);
    }
    
    // 벡터 값의 두번째에 해당하는 play의 합산 시간을 기준으로 정렬
    std::sort(arr.begin(), arr.end(), [] (auto x, auto y) {return x.second > y.second;});
    
  
    // 가장 시간이 긴 장르부터 genres / plays 탐색 --> seq 벡터에 넣기
    vector<pair<int, int> > seq;
    for (int i=0; i<arr.size(); i++) {
        
        for (int j=0; j<genres.size(); j++) {
            if (genres[j] == arr[i].first) {
                seq.emplace_back(plays[j], j);
            }
        }
        // seq 벡터에는 장르 별 play 시간 및 index가 들어가 있고, 이를 play 시간 기준으로 sorting
        std::sort(seq.begin(), seq.end(), [] (auto x, auto y) {return x.first > y.first;});
        for (int i=0; i<seq.size(); i++) {
            if (i<2) {
                // 가장 시간이 긴 장르 2개만 추출하여 answer에 넣기
                answer.emplace_back(seq[i].second);
            }
            
        }
        // 다음 장르를 위해 seq는 초기화해주기
        seq.clear();
    }
    
    return answer;
}

___