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

 

 

 

 

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

코딩테스트 연습 - 베스트앨범

매우 고려하기 복잡했던 문제

 

나는 일단 내가 원하는 대로 vector를 만들어서 하나씩 정렬해갔다.

 

주어진 genres, plays를 하나로 합친 vector => v

 

v의 형식은 (플레이횟수, (고유번호, 장르))로 했다.

 

v를 sort로 정렬하게 되면, 플레이 횟수로 v가 정렬된다.

나중에 "장르 내에서 많이 재생된 노래를 먼저 수록합니다." 조건을 만족시킬 수 있게 됐다.

 

그런 다음에 "속한 노래가 많이 재생된 장르를 먼저 수록합니다." 만족시키기 위해, genres vector를 중복 원소가 없도록 제거했다.

 

이제 중복 원소가 제거된 genres를 가지고 v를 돌면서 어떤 장르가 많이 재생됐는지 genres_sum에 (재생수, 장르) 형식으로 저장했다.

 

마지막으로 genres_sum에 저장된 장르 순서대로 v를 돌면서 많이 재생된 장르 내에서 많이 재생된 노래를 answer에 삽입했다.

 

** 여기서 고려해야할점

1. "스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다." 

> 두 개씩만 answer에 넣어야 해서 하나씩 answer에 삽입할 때마다 flag를 1씩 증가시켰다. flag가 3이 되면 세 번째 노래이므로 break

 

2. "장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다."을 만족시켜야 한다.

> 그래서 flag == 2일때, 즉 두 번째 노래를 삽입할 때 이전에 삽입했던 노래와 재생 횟수가 같은데 현재 고유번호가 더 낮은 수라면 swap해줬다.

 

Code

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    vector<pair<int, pair<int, string>>> v;
    
    for(int i=0; i<genres.size(); i++) {
        v.push_back(make_pair(plays[i], make_pair(i, genres[i])));
    }
    
    // 내림차순 정렬 - 장르 내에서 많이 재생된 노래를 먼저 수록 위해
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    
    //for(int i=0; i<v.size(); i++) {
    //    cout << "v1 : " << v[i].first << "\n";
    //    cout << "v2 : " << v[i].second.first << "\n";
    //    cout << "v3 : " << v[i].second.second << "\n";
    //}
    
    // genres 원소 중복 제거
    sort(genres.begin(), genres.end());
    genres.erase(unique(genres.begin(), genres.end()), genres.end());
    
    vector<pair<int, string>> genres_sum;

    // 많이 재생한 장르 찾기
    for(string g : genres) {
        int sum = 0;
        for(int i=0; i<v.size(); i++) {
            if(g == v[i].second.second) {
                sum += v[i].first;
            }
        }
        genres_sum.push_back(make_pair(sum, g));
    }
    
    // 내림차순 정렬 - 속한 노래가 많이 재생된 장르를 먼저 수록 위해
    sort(genres_sum.begin(), genres_sum.end());
    reverse(genres_sum.begin(), genres_sum.end());
    
    int flag = 1, before_listen, before_idx;
    
    for(int j=0; j<genres_sum.size(); j++) {
        for(int i=0; i<v.size(); i++) {
            if(flag == 3) break;
            if(flag == 1) {
                before_listen = v[i].first;
                before_idx = v[i].second.first;
            }
            if(genres_sum[j].second == v[i].second.second) {
                // 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
                if(flag == 2 && before_listen == v[i].first && before_idx > v[i].second.first) {
                    int tmp = answer.back();
                    answer.pop_back();
                    answer.push_back(v[i].second.first);
                    answer.push_back(tmp);
                }
                else {
                    answer.push_back(v[i].second.first);
                }
                flag += 1;
            }
        }
        flag = 1;
    }
    
    //for(int i=0; i<answer.size(); i++) {
        //cout << "answer : " << answer[i] << "\n";
    //}
    
    return answer;
}