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

베스트앨범 문제 주소

코딩테스트 연습 - 베스트앨범 | 프로그래머스

 

시간을 꽤 오래들여서 해결한 문제이다. 문제의 조건이 매우 까다로워서 고려해야하는 것이 많다보니 작은 실수에도 원하는 답이 나오지않게된다. 조건을 살펴보자.

 

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

여기서 알아낼 수 있는 정보를 모두 알아내어 정리하자면 다음과 같다.

 

1) 모든 장르의 재생된 횟수가 다르니 장르의 재생수가 같은 경우는 고려할 필요가 없다.

2) 속한 노래가 많이 재생된 장르를 먼저 수록한다. 즉 3600번 재생된 장르의 곡 중 하나가 다른 2000번 재생된 장르의 곡 하나 보다 재생수가 적더라도 장르를 먼저 우선순위로해서 3600번 재생된 장르의 곡을 먼저 싣는다.

3) 곡을 실을 때는 한 장르당 최대 2곡까지 실을 수 있다. 1개 내지 2곡이 베스트앨범에 들어간다는 소리다.

4) 장르 내에서 곡의 재생수가 같으면 고유번호가 낮은 것 부터 실은다. A곡이 300번 재생 B곡이 300번 재생일 때 A의 고유번호가 1이고 B의 고유번호가 2이면 A를 먼저 베스트앨범에 넣는다는 뜻이다.

 

위의 4가지 정도만 고려하면은 풀 수있을 것 같다.

난 다음과 같은 과정으로 해결했다.

 

1) {장르 : [곡리스트(인덱스포함)]}의 딕셔너리 구조로 저장을 했다. (map 클래스를 사용)

2. 장르별 재생수의 총합을 구하기 위한 vector 리스트를 하나 더 만들었다.

3) 장르별 곡의 재생수 총합을 먼저 구한다.

4) 재생수 기준으로 장르를 정렬한다.

5) 딕셔너리 구조로 저장한 장르안의 곡 리스트들을 재생수 순으로 정렬한다. 재생수가 같을시 인덱스가 낮은 곡을 우선순위로 정렬한다.

6) 최대 상위 2개까지 많이 재생된 장르의 많이 재생된 곡을 정답 리스트에 넣는다.

 

해야될게 많아져버리니까 뇌절이 와버린다.

내 코드도 정답을 맞추기는 했지만 너무나도 복잡한 코드가 되어버렸다.

맵안에 벡터 이름을 참조해서 해당 인덱스의 벡터안의 ..... 이런식의 구조로 짜여있다.

코드를 쉽게 수정할 엄두가 안나서 이대로 내비뒀다.

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

struct tsum{
    int sum;
    string name;
};

//장르 정렬
bool comp(tsum a, tsum b){
    return a.sum > b.sum;
}

//곡 정렬
bool idxcomp(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; //정답
    map<string, vector<pair<int, int>>> mp; // 장르와 곡리스트(인덱스와 함께)들
    vector<tsum> t_sum; //장르의 총 재생수와 인덱스, 장르명
    
    //자료구조
    //{"classic":[500, 150, 800], "pop":[600, 2500]}
    for(int i = 0; i < genres.size(); i++){
        mp[genres[i]].push_back({plays[i], i});
    }
    
    // 장르 합이 제일 큰것을 찾기
    for(auto m = mp.begin(); m != mp.end(); m++){
        int sum = 0;
        for(int j = 0; j < genres.size(); j++){
            if(m->first == genres[j]){
                sum += plays[j];
            }
        }
        t_sum.push_back({sum, m->first});
    }
    // 장르 합이 큰것부터 정렬한다.
    sort(t_sum.begin(), t_sum.end(), comp);
    
    // 정렬된 키 순으로 2개씩 구하기
    for(auto m = mp.begin(); m != mp.end(); m++){
        // 정렬을 하되 인덱스도 고려하면서 정렬
        sort(m->second.begin(), m->second.end(), idxcomp);
    }
    
    //재생수가 많은 장르부터 반복문 시작
    for(int i = 0; i < t_sum.size(); i++){
        // 아래 반복 조건은 장르의 갯수 만큼이면서 2개 미만인 경우다 즉 1개 혹은 2개만 추출한다.
        for(int j = 0; j < mp[t_sum[i].name].size() && j < 2; j++){
            //곡이 정렬되어 있는 장르에서 상위 2개의 곡의 인덱스를 꺼낸다.
            answer.push_back(mp[t_sum[i].name][j].second);
        }
    }
    return answer;
}