프로그래머스 - 베스트앨범 - Level 3

문제

풀이전략

1. 어떤 장르가 가장 많은지, 그 장르들 중에 무엇이 제일 큰지를 알아야한다. 따라서 전체 노래 재생된 횟수의 따라 sort를 하고, 같은 장르중에 또 크기별로 따로 sort해야한다.
2. 구조체를 선언하여 장르를 구분하고, 구조체 내부에 또 vector를 선언하여 각 장르마다 몇개의 어떤 index의 play가 제일 큰지 또 한번 정렬을 해야한다.

코드

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
// 구조체를 선언했다. 보면 whole은 전체 플레이횟수를 저장한다. 
// playId는 벡터로, 횟수와 index가 저장된다. 
struct song{
    string genre;
    vector<pair<int, int> > playId; 
    int whole;
    song(string a, int b, int c, int d){
        genre = a;
        playId.push_back(make_pair(b, c));
        whole = d;
    }
    // 이 구조체는 whole이 큰 순으로 정렬하도록 만들었다. 
    bool operator<(const song& otherSong) const{
        return whole>otherSong.whole;
    }
};
// 같은 장르 내에서 재생횟수가 높은 index순으로 정렬
// 만약 재생횟수가 같다면, 더 index가 빠른 순으로 정렬함
bool mySort(pair<int, int> a, pair<int, int> 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;
    vector<song> s;
    // song벡터에 값을 넣는 과정
    for(int i=0; i<genres.size(); i++){
    	// 해당하는 장르가 이미 생성 되었는지 아닌지를 체크하는 flag
        bool flag = true;
        for(int j=0; j<s.size(); j++){
            if(s[j].genre == genres[i]){
                flag = false;
                s[j].playId.push_back(make_pair(plays[i],i));
                // 어떤 장르가 가장 많이 재생되었는지를 체크하는 whole
                s[j].whole += plays[i];
            }
        }
        // 새로운 장르일경우 push_back해준다. 
        if(flag) s.push_back(song(genres[i], plays[i], i, plays[i]));
    }
    sort(s.begin(), s.end());
    for(int i=0; i<s.size(); i++){
        sort(s[i].playId.begin(), s[i].playId.end(), mySort);
        for(int j=0; j<=1; j++){
            if(j == s[i].playId.size()) break;
            answer.push_back(s[i].playId[j].second);
        }
    }
    return answer;
}

다른분 코드

// 나는 여전히 unorderd_map 사용에 능숙하지 못하다. 
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>

using namespace std;
// 장르 내에서 무엇이 많이 재생되었는지 비교해주는 함수이다. 
bool compare (pair<int, int> left, pair<int, int> right){
    if(left.first > right.first){
        return true;
    }else if(left.first == right.first){
        if(left.second < right.second){
            return true;
        }
    }
    return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    // 어떤 장르가 가장 많이 재생되었는지를 확인하기위한 맵
    unordered_map<string, int> summap;
    // 각 장르마다 어떤 index의 곡이 많이 재생되었는지를 확인하기 위한 맵
    unordered_map<string, vector<pair<int, int>>> genmap;
    // 이 과정이 어떻게 보면 비 효율적으로 보이지만 O(n)으로 해결할 수 있는 방법이다.
    for (int i = 0; i < genres.size(); i++) {
        summap[genres[i]] += plays[i];
        genmap[genres[i]].push_back(make_pair(plays[i], i));
    }
    // O(n)으로 해결하기위해 비 효율적으로 메모리를 사용했지만 그래도 빠르니까 .... 
    vector<pair<int, string>> fororder;
    for (auto x : summap) {
        fororder.push_back(make_pair(x.second, x.first));
    }
    sort(fororder.begin(), fororder.end());
    while (fororder.size() > 0) {
        pair<int, string> temp= fororder.back();
        fororder.pop_back();
        vector<pair<int, int>> a = genmap[temp.second];
        sort(a.begin(), a.end(), compare);
        int lastn = 2;
        if (a.size() < 2) {
            lastn = a.size();
        }
        for (int i = 0; i < lastn; i++) {
            answer.push_back(a[i].second);
        }
    }

    return answer;
}

소감

여러개의 값들을 비교하면서 또 탐색을 해야해서 인상적이였던 문제였다. unordered_map을 사용하는 다른 분의 풀이도 잘 알아둬야한다. 내 풀이는 너무 sort함수를 많이 사용하였다고 생각하기 때문이다.