Programmers: 베스트 엘범

문제

• Hash, LV3
• https://programmers.co.kr/learn/courses/30/lessons/42579

문제 이해

• 장르가 주어지고, 얼마나 틀어졌는데 수가 각각 주어진다
• 고유번호 = 인덱스
• "장르 별 최대 2개" 이다.
  • 문제에서 주어진 예를 따지면,
    • Classic 2개, Pop 2개를 따져서 리턴 해야된다
    • 이 때, answer.size = 4
  • 그럼 문제에서 주어진 예 말고, 특정한 장르에 곡이 1개만 있다면?
    • 그러면 2개를 리턴하는 것이 아닌 1개를 넣어서 리턴해야됨

문제 입력 예시를 보기!

0. 입력을 맵[해쉬맵]으로!

장르	1	2	3	합
classic	500	150	800	1450
pop	600	2500		3100

이렇게 생기게 됩니다!
해쉬맵의 키는 장르, 값은 노래 플레이 수 입니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

• 일단 보면 장르 2개 중, 노레 플레이 수의 합이 가장 큰 것은 Pop입니다.
• 따라서 먼저 Pop에 있는 노래 2개를 수록하고, Classic에 있는 노래 2개를 수록하게 됩니다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

• 각 장르별로 한번 보면,
  • Pop 장르에서는 2500, 600 순입니다.
  • Classic 장르에서는 800, 500 순입니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유번호가 낮은 노래를 먼저 수록합니다.

• 해당 예제에서는 그런 경우가 없어서 넘어갑니다.

4. 답은 구했으니, 인덱스만 고려합니다.

• 2번 부분에서 답은 이미 구했으니, 인덱스만 고려합니다.
  • Pop장르에서는 2500이 4번 인덱스, 600이 1번 인덱스 입니다.
  • Classic 장르에서는 800이 3번 인덱스, 500이 0번 인덱스 입니다.

결국 답은 = [4, 1, 3, 0]이 됩니다.

특수경우

장르에 곡이 단 1개만 수록된 경우

• 곡이 1개만 수록된 경우, 다 필요 없고 그 한 곡만 수록됩니다.[단 1번을 끝내고 그 순서에 따라서!]
• 문제 이해 부분에서 2개가 '최대' 라고 한 얘기가 이 얘기입니다.
  • 장르에 곡이 1개만 수록된 경우, 1개 그대로 올라가기 때문입니다!

알고리즘

• 일단 입력[장르/플레이 횟수]를 맵으로 바꿔줍니다.
  • 멥은 키 = 장르, 값 = 플레이 횟수 벡터와[이하 a맵], 키 = 장르, 값 = 플레이 총합[이하 b맵] 2개를 구성했습니다.
  • a맵에서 각 플레이 벡터를 정렬해줍니다.[큰 것 순으로]
  • b맵을 플레이 총합 순으로 정렬하기 위해 벡터[이하 b벡터]로 변환하고, 정렬합니다.
• b벡터를 순회하면서[b벡터는 정렬 되어있기 때문에 이미 1번 과정이 완료 된 것입니다.]
  • b벡터에 담겨있는 a맵의 키를 가져오고
  • a맵의 키에 해당하는 벡터를 가지고 옵니다.
  • a맵의 키에 해당하는 벡터의 사이즈가 2보다 작으면[없는 경우는 없으니]
    • answer에 단 하나의 원소만 push합니다.
  • 그 이외에 2개면 순서대로 answer에 push합니다.

코드

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

using namespace std;

class Test {
public:
    int num;
    int plays;

    Test(int num = 0, int plays = 0) {
        this->num = num;
        this->plays = plays;
    }
};

bool contains(unordered_map<string, vector<Test>>& target, string key) {
    return (target.find(key) != target.end()); 
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, vector<Test>> map_array;
    unordered_map<string, int> each_size;

    // Input to map
    for (int i = 0; i < genres.size(); i++) {
        if (!contains(map_array, genres[i])) {
            map_array.insert(make_pair(genres[i], vector<Test>{Test(i, plays[i])}));
            each_size.insert(make_pair(genres[i], plays[i]));
        } else {
            each_size[genres[i]] += plays[i];
            map_array[genres[i]].push_back(Test(i, plays[i]));
        }
    }

    // Sort map itself
    for (auto it = map_array.begin(); it != map_array.end(); it++) {
        sort(it->second.begin(), it->second.end(), [](Test one, Test two) {
            if (one.plays == two.plays) {
                return one.num < two.num;
            }
            return one.plays > two.plays;
        });
    }

    // Sort
    vector<pair<string, int>> sorted_vector(each_size.begin(), each_size.end());
    sort(sorted_vector.begin(), sorted_vector.end(), [](pair<string, int> one, pair<string, int> two) {
        return one.second > two.second;
    });

    for (int i = 0; i < sorted_vector.size(); i++) {
        string key_name = sorted_vector[i].first;
        vector<Test>& value_using = map_array[key_name];
        if (value_using.size() < 2) {
            answer.push_back(value_using[0].num);
        } else {
            answer.push_back(value_using[0].num);
            answer.push_back(value_using[1].num);
        }
    }

    return answer;
}