[프로그래머스 코딩테스트 고득점 Kit - 해시] 베스트앨범

해시 문제

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

 

---

[문제 풀이]

 

총 재생 수대로 장르를 정렬하고 장르 내에서도 가장 많은 재생 수와 두 번째로 많은 재생 수를 가진 고유 번호를 순서대로 출력하는 문제입니다.

 

문제를 이해하는 것조차 쉽지 않습니다.

요약하자면, 총 재생 수대로 장르를 정렬하고 그 장르 내에서도 가장 많은 재생 수를 가진 두 곡을 차례로 answer에 넣는 문제입니다.

단, 한 장르 내에 곡이 한 개인 경우 한 곡만 넣습니다.

 

 

한 번에 하려고 하면 머리가 아프니 한 개씩 천천히 생각해 봅시다.

 

우선 장르 별로 정렬할 필요가 있으니 장르 별 총 재생 수를 기록합시다.

이 과정까지는 간단한 해시 문제입니다.

맵을 하나 만들어 key로 장르 이름을 넣고 value로는 재생 수를 계속 더하면 됩니다.

 

그리고 value를 기준으로 내림차순 정렬을 해줘야 하지만, 맵에는 value를 기준으로 정렬하는 기능이 없습니다.

vector에 옮긴 후 pair.second를 기준으로 내림차순 정렬을 시켜주면 정렬이 가능합니다.

 

이제 장르끼리의 정렬은 끝났습니다.

하지만 장르 내의 곡은 기록하지 않았습니다.

이를 위해 맵을 한 개 더 만들겠습니다.

 

그러나 장르 내에서 가장 많이 재생된 노래를 찾기 위해 넣어야 하는 재생 수와, answer에 넣어줘야 하는 고유 번호가 필요하므로 두 정수를 저장할 클래스(구조체)를 이용합니다.

재생 수를 기준으로 최댓값을 구할 수 있어야 하므로 < 연산자를 오버로딩 해주는 과정도 필요합니다.

 

맵을 한 개 더 만들어 key는 장르 이름으로, value는 클래스(구조체) 배열로 설정합니다.

 

이제 총 재생수로 정렬한 vector를 순회하면서 클래스(구조체) 배열의 최댓값을 answer에 넣고, 최댓값을 삭제한 후의 최댓값(두 번째로 큰 값)을 또 answer에 넣습니다.

모든 장르마다 위의 과정을 반복하면 정답을 도출할 수 있습니다.

 

주의할 점은 장르내에 곡이 한 개뿐인 경우를 예외 처리해 주어야 합니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

class Album {
public:    
    int idx, play;
    
    Album (int idx, int play) {
        this->idx = idx;
        this->play = play;
    }
    
    bool operator<(const Album& a) {
        return play < a.play;
    }
};

bool cmp (const pair<string, int> &p1, const pair<string, int> &p2) {
    return p1.second > p2.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    unordered_map<string, int> total;
    unordered_map<string, vector<Album>> lst;
    vector<int> answer;
    
    int N = genres.size();
    for (int i = 0; i < N; i++) {
        string s = genres[i];
        int n = plays[i];
        
        if (!total.insert(make_pair(s, n)).second) {
            total[s] += n;
        }
        
        lst.insert(make_pair(s, vector<Album>()));
        lst[s].push_back(Album(i, n));
    }
    
    vector<pair<string, int>> vct (total.begin(), total.end());
    sort(vct.begin(), vct.end(), cmp);
    
    for (pair<string, int> p : vct) {
        string s = p.first;
        
        vector<Album>::iterator iter = max_element(lst[s].begin(), lst[s].end());
        answer.push_back(iter->idx);
        lst[s].erase(iter);
        
        if (lst[s].size() > 0) {
            iter = max_element(lst[s].begin(), lst[s].end());
            answer.push_back(iter->idx);
        }
    }
    
    return answer;
}

 

---

[메모]

 

• 템플릿만 동일하다면 stl의 종류와 관계없이 복사가 가능하다.
• map의 정렬 기준을 변경하는 것은 vector로 옮긴 후 가능하다.
• set의 정렬 기준은 템플릿 뒤에 정렬 기준을 추가할 수 있다.
• vector의 최댓값은 max_element로 구할 수 있다. iterator 타입으로 반환