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

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

오늘은 프로그래머스 [해시] 문제들을 풀어봤다.

그 중 베스트앨범이라는 문제를 포스팅 해볼까 한다.

[해시] 문제인 만큼 map이나 set을 최대한 활용해 보려고 노력했다.

문제 설명을 간단히 하자면

스트리밍 사이트에서 가장 유명한 노래들을 모아 베스트앨범을 만들고자 한다.

앨범에는 장르당 두 노래씩 넣는다.(여기 때문에 조금 헤맸다) 

1. 가장 많이 재생된 장르부터 앨범에 넣는다.

2. 두 곡의 순서는 더 많이 재생된 노래 먼저 넣는다.

3. 만약 두 곡의 재생횟수가 같으면 고유번호(인덱스)가 더 낮은 것 부터 넣는다.

그 후 최종적으로 answer 벡터에 값을 넣어 반환하면 된다.

그런데 제한사항으로

만약 장르에 노래가 한 곡밖에 없다면 한 곡만 넣어야 한다는 말이 있다.

내가 이걸 못 봐서 처음에 53.3점인가 맞았었다. 문제를 잘 보자.

해결 아이디어는 map과 pair를 사용해서 해결했다.

프로그래머스 첫 포스팅이니 하나하나 설명하겠다.

1. 가장 많이 재생된 장르부터 앨범에 넣는다.

먼저 각 장르마다 재생횟수를 알기위해 map을 이용한다.

key값을 string, value값을 int로 하는 map을 하나 만든다.

장르 벡터를 모두 탐색하면서 장르를 key값으로 map에 넣는다.

여기서 map에 이미 들어가 있던 장르라면

기존의 데이터 셋에서 value를 가지고와 현재 노래의 재생횟수를 더 해준다.

map에 처음 들어가는 장르라면

key값에 장르, value값에 재생횟수를 넣어준다.

탐색이 끝난 후엔 key값에 장르, value값엔 장르의 총 재생횟수가 들어간 map이 완성된다.

그렇지만 map은 균형이진트리이므로 key를 우선으로 오름차순 정렬이 된다.

우린 이걸 재생횟수 기준으로 내림차순 정렬을 해야한다.

가장 많이 재생된 장르 순서대로 앨범에 넣야 하기 때문이다.

근데 compare함수를 만들어서 하기엔 너무 복잡했다.

그래서 그냥 key값을 int, value값을 string으로하는 map을 하나 더 만들었다.

그후 key값에 아까 만들었던 map의 value, 즉 총 재생횟수를 -(음수)로 넣고 vlaue값에 장르를 넣는다.

아까 말했듯이 key를 우선으로 오름차순 정렬이기 때문에 내림차순 정렬로 쓰고 싶을 땐

-(음수)를 붙여서 집어 넣으면 알아서 내림차순이 된다.

ex) 2 4 9 6 8를 -(음수)붙이고 정렬하면 => -9 -8 -6 -4 -2 가 된다.

우리가 필요한건 값 자체가 아니라 값과 한 세트인 장르의 순서이므로 이렇게 해도 문제가 없다.

다만 이렇게 하기 위해선 아주 중요한 조건이 필요하다.

바로 장르의 총 재생횟수가 유일해야한다.

그래야만 key 값으로 사용할 수 있기 때문이다.

제한 사항을 다시 보면 모든 장르는 재생된 횟수가 다릅니다. 라고 써있으므로 이렇게해도 문제 없다.

2. 두 곡의 순서는 더 많이 재생된 노래 먼저 넣는다.

3. 만약 두 곡의 재생횟수가 같으면 고유번호(인덱스)가 더 낮은 것 부터 넣는다.

여기까지 왔으면 이제 거의 다 왔다.

이젠 내림차순으로 정렬했던 map을 가지고 탐색하면서

장르가 같은 노래들을 모두 벡터나 배열에 넣어주고

정렬 후 두개를 answer벡터에 넣으면 된다.

여기서 pair를 사용했다. 두 가지 값 모두 int 형식이며

첫 번째 값은 재생횟수, 두 번째 값은 고유번호를 넣어주었다.

여기서도 마찬가지로 재생 횟수는 내림차순으로 해야되니 음수로 넣어주고

고유번호는 오름차순이니 그냥 넣어주었다.

pair의 정렬은 참 고마운게 첫 번째 데이터 값이 같을 경우 자동으로

두 번째 값 기준으로 정렬을 해준다.

물론 compare함수를 따로 만들지 않으면 오름차순이다.

즉, 고유번호가 낮은 것 부터로 정렬이 된다.

이렇게 모든 장르마다 배열에 넣고 정렬하는 것을 해주고

가장 위에있는 두 노래를 answer벡터에 넣어주면된다.

만약 장르에 해당하는 노래가 하나 밖에 없다면 하나만 넣어주면 된다.

끝.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> mp;
    map<string, int>::iterator it;
    for(int i=0; i<(int)genres.size(); i++){
        it = mp.find(genres[i]);
        if(it != mp.end()){
            int pre = it->second;
            mp[genres[i]] = pre+plays[i];
        }else{
            mp.insert({genres[i], plays[i]});
        }
    }
    map<int, string> rev;
    map<int, string>::iterator rit;
    for(it = mp.begin(); it != mp.end(); it++){
        rev.insert({-(it->second), it->first});
    }
    pair<int, int> arr[10010];
    for(rit = rev.begin(); rit != rev.end(); rit++){
        string gen = rit->second;
        memset(arr, 0, sizeof(arr));
        int idx = 0;
        for(int i=0; i<(int)genres.size(); i++){
            if(gen.compare(genres[i]) == 0){
                arr[idx++] = {-plays[i], i};
            }
        }
        sort(arr, arr+idx);
        if(idx==1){
            answer.push_back(arr[0].second);             
        }else{
            answer.push_back(arr[0].second);
            answer.push_back(arr[1].second);     
        }
    }
    
    return answer;
}