[DAY86] Algorithm : Best Album

장르별로 가장 많이 재생된 노래를 두 곡씩 뽑아 앨범을 만드는 문제다. 여러 정렬 기준(장르 총합 $\rightarrow$ 노래 재생 수 $\rightarrow$ 고유 번호)을 만족시켜야 한다. 해시(Hash)를 이용해 데이터를 집계하고, 음수 변환(-1) 테크닉을 활용해 복잡한 비교 함수 없이 기본 정렬만으로 해결했다.

---

❓ 문제 분석

• 목표: 조건에 맞춰 노래의 고유 번호를 순서대로 반환하기.
  1. 속한 노래가 많이 재생된 장르 먼저.
  2. 장르 내에서 많이 재생된 노래 먼저 (내림차순).
  3. 재생 횟수가 같으면 고유 번호가 낮은 노래 먼저 (오름차순).
• 제약 조건: 장르 종류는 100개 미만, 곡 수는 10,000개 이하.
• 핵심 키워드: "장르 별 집계", "다중 정렬 조건", "해시".

---

💡 풀이 설계

1. 자료구조 설계 (Data Structure)

• 데이터를 효율적으로 관리하기 위해 두 개의 unordered_map을 사용했다.
  1. genre_total: 장르별 총 재생 횟수 (string $\rightarrow$ int)
  2. genre_songs: 장르별 노래 리스트 (string $\rightarrow$ vector<pair>)

2. 핵심 아이디어 (The Trick: Negative Sorting)

• 노래 정렬: "재생 수 내림차순 + 고유 번호 오름차순"을 동시에 만족해야 한다.
  • 보통은 커스텀 비교 함수(cmp)를 짜야 하지만, 재생 수에 -1을 곱해서 저장하면 C++ 기본 sort(오름차순)만으로 해결된다.
  • 예: (500회, 1번), (300회, 2번) $\rightarrow$ {-500, 1}, {-300, 2} 로 저장.
  • 정렬 시: -500이 -300보다 작으므로 앞에 옴 $\rightarrow$ 자연스럽게 재생 수 내림차순 효과!
  • 재생 수가 같다면(-500 == -500): pair의 두 번째 원소인 고유 번호(1, 2)는 오름차순 정렬됨. $\rightarrow$ 조건 완벽 충족.
• 장르 정렬: 장르 역시 총 재생 수에 -1을 곱해 정렬하여, 재생 수가 많은 장르가 먼저 오도록 처리한다.

---

💻 코드 구현

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

using namespace std;

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

    // 데이터 집계
    unordered_map<string, int> genre_total;
    unordered_map<string, vector<pair<int, int>>> genre_songs;

    for (int i = 0; i < genres.size(); i++) {
        genre_total[genres[i]] += plays[i];
        // {-재생수, 고유번호} 형태로 저장하여 정렬 로직 단순화
        genre_songs[genres[i]].emplace_back(-plays[i], i);
    }

    // unorded_map을 뒤집어 장르 랭킹 산정
    // 키 중복 문제를 예방하기 위해 vector 사용 {-총재생수, 장르명}
    vector<pair<int, string>> genre_rank;
    for (auto const& item : genre_total) {
        genre_rank.push_back({-item.second, item.first});
    }
    
    // -총재생수 기준 오름차순 정렬 (실제로는 총재생수 내림차순 효과)
    sort(genre_rank.begin(), genre_rank.end());

    // 정답 추출
    for (auto const& item : genre_rank) {
        string genre = item.second;
        vector<pair<int, int>>& songs = genre_songs[genre];
        
        // pair 정렬: 첫 번째(-재생수) 오름차순 -> 두 번째(고유번호) 오름차순
        sort(songs.begin(), songs.end());
        
        // 장르 별 최대 2곡까지 수록
        for (int i = 0; i < songs.size(); ++i) {
            if (i == 2) break;
            answer.push_back(songs[i].second);
        }
    }
    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점 1: 처음에는 장르 순서를 정렬하기 위해 map<int, string>을 사용했다.
• 원인: map은 키(Key)의 중복을 허용하지 않는다. 만약 'Pop'과 'Rock'의 총 재생 수가 같다면, 나중에 들어온 장르가 덮어씌워져 데이터가 사라지는 치명적인 버그가 발생한다.
• 해결: vector<pair>에 담아서 sort하는 방식으로 변경하여 중복 재생 수 문제 없이 안전하게 정렬했다.
• 문제점 2: 복잡한 cmp 함수 작성 시 실수가 잦았다.
• 해결: 데이터를 저장할 때부터 -1을 곱하는 방식을 선택했다. 덕분에 별도의 비교 함수 없이 STL sort의 기본 동작만으로 다중 정렬 조건을 깔끔하게 해결했다.

---

✅ 오늘의 회고

항목	내용
유형	Hash (해시), Sorting (정렬)
체감 난이도	상 (자료구조 설계와 정렬 기준이 복합적임)
복잡도	시간: $O(N \log N)$, 공간: $O(N)$
새로 배운 것	1. 음수 변환(-1) 테크닉: 오름차순 정렬을 내림차순처럼 쓰는 꿀팁. 2. map 사용 시 Key 중복에 의한 데이터 유실 주의.

---