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

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

프로그래머스

 

장르이름과 재생횟수가 따로 배열로 주어지고, 각 노래는 고유번호 즉 인덱스로 구분한다.

구해야 할 것은 일단

- 장르별 전체 재생횟수의 합, 순서대로 정렬

- 장르 안에서 재생횟수(같으면 고유번호) 순서대로 정렬

 

뭔가 이런저런 시도를 해봤는데 역시 "고유번호"가 유지되어야 한다는 점이 거슬렸다. 대충 벡터에 넣어서 소트하자니 순서도 없어지고... 장르별로 소트를 하고 그 안에서 또 따로따로 소트가 되어야 하고...

결국에는 map을 사용해서 풀었다.

장르 이름을 key로 하고, value에 해당 장르의 곡들 정보를 담았다. 단 이때 고유번호가 저장되어야 하므로 {재생횟수, 고유번호}의 pair 형태로 각 곡을 관리하고, 장르별 곡들은 vector에 담아 한번에 관리한다.

 

typedef pair<int, int> ci;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int n = genres.size();

    map<string, vector<ci>> hash_map;
    for(int i=0;i<n;i++){
        hash_map[genres[i]].push_back(make_pair(plays[i], i));
    }

재생횟수를 first, 고유번호를 second에 넣은 건 기본적으로 pair가 first를 기준으로 정렬하고 같다면 second를 기준으로 정렬하기에, 편하게 하려고 그랬다. 근데 이때까지만 해도 문제를 대충 읽어서 고유번호는 오름차순이라는 걸 몰랐다(....) ;

여튼 이렇게 데이터를 해시맵에 넣어준다. 이제 각 장르 안에서, 조회수에 따라(같으면 고유번호) 벡터를 정렬해줄 것이다.

 

말했듯 first가 재생횟수, second가 고유번호이다.

재생횟수는 내림차순으로 정렬해야 한다. 큰 게 먼저.

그리고 재생횟수가 같으면 고유번호 오름차순으로 정렬한다. 이 경우에는 작은 게 먼저.

compare 함수를 따로 만들어주고,

bool compare(ci a, ci b){
    if (a.first == b.first) return a.second < b.second;
    return a.first > b.first;
}

 

다시 솔루션 함수로 돌아와 각 해시맵의 value들을 정렬해준다.

    // 각 해시맵에서 value vector를 조회수별 정렬
    for(auto &iter: hash_map){
        sort(iter.second.begin(), iter.second.end(), compare);
    }

 

준비가 끝낫다

이제 장르의 전체 재생횟수를 구하고, 횟수 합의 내림차순으로 장르를 정렬하자.

그건 또 어디에 저장해둘 것인가!< 이것도 고민이 많았는데 결국 <int(총 재생횟수), string(장르이름)> pair를 갖는 vector로 선언하였다. 이번에도 총재생횟수가 앞으로 온 이유는 정렬하기 편하라고! 이다. string이 먼저 오면 알파벳 순으로 정렬될테니...

    vector<pair<int, string>> cnt;
    for(auto iter: hash_map){
        int tmp = 0;
        for(auto p: iter.second){
            tmp += p.first;
        }
        cnt.push_back(make_pair(tmp, iter.first));
    }
    
    sort(cnt.begin(), cnt.end(), greater<>());

각 해시맵 value들을 돌며 재생횟수를 모두 더해주고, cnt라는 배열에 저장.

다했으면 cnt를 내림차순 정렬해줘서 장르들의 순서를 결정해준다.

 

이제 다했다

cnt에 저장된 장르 순서대로, 해당 장르의 value 중 제일 앞에 있는 두 개를 뽑아서 answer 배열에 추가해주기만 하면 된다. (이미 위에서 정렬했으니까)

    // cnt에 횟수를 내림차순으로 저장 (횟수, 장르이름) pair
    // cnt의 첫번째 요소부터, 각 장르에서 2개씩 선정
    for(int i=0;i<cnt.size();i++){
        string cur_genre = cnt[i].second; // 장르명
        vector<ci> cur_arr = hash_map[cur_genre]; // 해당 장르의 곡들 (정렬상태)
        answer.push_back(cur_arr[0].second); // 상위 2개의 고유번호
        if(cur_arr.size() > 1){
            answer.push_back(cur_arr[1].second);
        }
    }

어느 배열/맵에 어떤 데이터가 저장되어 있는지만 잘 따져주면 된다.

그리고 문제에서 곡이 한개일 경우에는 그거 하나만 저장한댔으니 조건문까지 맞게 설정해주면 진짜 끝.

 

문제는 정말 단순한데..... 이걸 뭘 어따가 저장하지 <<- 이거 때문에 오래 걸렸다 ㅜ  ㅜ. 결국엔 맵이랑 벡터밖에 없는데도.... 아직도 뚝딱뚝딱거리는 중

 

🖥️ 전체 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int, int> ci;

bool compare(ci a, ci b){
    if (a.first == b.first) return a.second < b.second;
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int n = genres.size();

    map<string, vector<ci>> hash_map;
    for(int i=0;i<n;i++){
        hash_map[genres[i]].push_back(make_pair(plays[i], i));
    }
    
    // 각 해시맵에서 value vector를 조회수별 정렬
    for(auto &iter: hash_map){
        sort(iter.second.begin(), iter.second.end(), compare);
    }
    
    vector<pair<int, string>> cnt;
    for(auto iter: hash_map){
        int tmp = 0;
        for(auto p: iter.second){
            tmp += p.first;
        }
        cnt.push_back(make_pair(tmp, iter.first));
    }
    
    sort(cnt.begin(), cnt.end(), greater<>());
    
    // cnt에 횟수를 내림차순으로 저장 (횟수, 장르이름) pair
    // cnt의 첫번째 요소부터, 각 장르에서 2개씩 선정
    for(int i=0;i<cnt.size();i++){
        string cur_genre = cnt[i].second; // 장르명
        vector<ci> cur_arr = hash_map[cur_genre]; // 해당 장르의 곡들 (정렬상태)
        answer.push_back(cur_arr[0].second); // 상위 2개의 고유번호
        if(cur_arr.size() > 1){
            answer.push_back(cur_arr[1].second);
        }
    }
    return answer;
}