[프로그래머스] level 3 - 베스트앨범

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

코딩테스트 연습 - 베스트앨범 | 프로그래머스

본 문제는 해시와 정렬을 이용해야 하는 문제다. 결과를 장르별, 많이 재생된 노래, 고유 번호가 낮은 순으로 3가지 기준에 맞게 정렬해야 한다. 문제 해결 방법으로

1. 입력으로 들어오는 장르에 임의의 번호를 저장한다.
2. 장르별로 재생된 총횟수를 파악한다.
3. vector에 tuple로 장르, 재생 횟수, 고유 번호순으로 저장한다.
4. 이제 장르별, 재생 횟수, 고유 번호로 정렬을 한다.
5. 장르별로 최대 2개까지 선택한다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
vector<int> answer;
map<string, int> m1;
map<int, string> m2;
int d[101][2];
int k = 0;
 
bool cmp(tuple<int, int, int> i, tuple<int, int, int> j) {
    int x1, y1, z1;
    int x2, y2, z2;
    tie(x1, y1, z1) = i;
    tie(x2, y2, z2) = j;
    
    // 장르별 총 재생횟수가 같을 경우
    if (x1 == x2) {
        // 재생 횟수가 같을 경우
        if (y1 == y2) {
            // 고유 번호가 낮을 순서
            return z1 < z2;
        }
        // 재생 횟수가 큰 경우
        else return y1 > y2;
    }
    // 장르별 총 재생 횟수가 큰 경우
    else return x1 > x2;
}
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    for (int i = 0; i < genres.size(); i++) {
        m2.insert(make_pair(i, genres[i]));
        auto p = m1.find(genres[i]);
        if (p == m1.end()) {
            // 장르별 임의의 번호 저장
            m1.insert(make_pair(genres[i], k));
            d[k][0] = plays[i];
            // 마지막에 장르별 2개 선택을 위한 배열
            d[k][1] = 0;
            k += 1;
        }
        // 이미 저장된 장르일 경우 재생 횟수만 추가
        else d[p->second][0] += plays[i];
    }
    // 장르, 재생횟수, 고유 번호 순으로 저장
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < genres.size(); i++) {
        auto p = m1.find(genres[i]);
        v.push_back(make_tuple(d[p->second][0], plays[i], i));
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++) {
        int x, y, z;
        tie(x, y, z) = v[i];
        auto p = m1.find(m2.find(z)->second)->second;
        // 장르별 2개 선택
        if (d[p][1] < 2) {
            d[p][1] += 1;
            answer.push_back(z);
        }
    }
    return answer;
}

이 문제는 정말 프로그래머스스러운 문제다.