[C++] Programmers Lv. 3 "베스트앨범"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 간략화

장르 재생 횟수 > 곡 재생 횟수 > 고유 번호 순으로 정렬 후 장르 별로 최대 두 개씩 뽑아 answer에 push한 뒤 반환하면 되는 문제이다. 

 

입력으로 들어온 장르 별 재생 횟수를 저장하기 위해 unordered_map을 사용했다.

unordered_map<장르 이름, 장르 재생 횟수>로 장르 별 재생 횟수를 누적한다.

 

이후 제일 많이 재생된 장르에서 우선으로 곡을 뽑으므로, value 값인 장르 재생 횟수를 기준으로 정렬하기 위해 unordered_map<장르 이름, 장르 재생 횟수>을 vector로 변환 후 장르 재생 횟수 내림차 순으로 정렬한다.

 

music에 대한 세부 데이터(재생 횟수, 고유 번호)가 필요하므로 struct로 music 데이터를 만들어 주고, 

다시 한번 unordered_map을 사용해 (장르 - 해당 장르 곡들) 쌍을 만들어 준다.

정렬 후 장르 별로 최대 두 개씩만 뽑으면 되므로 이런 식으로 구조를 잡았다.

 

value 값인 해당 장르 곡들은 따로 비교 함수를 작성하여 곡 재생 횟수, 고유 번호 기준으로 정렬되게끔 했다.

모두 정렬 시키고 unordered_map<장르, 해당 장르 곡들>에서 장르 별로 접근한 다음, 해당 장르 곡들 중 첫 번째, 가능하다면 두 번째 원소 까지 answer에 push하였다.

 

🔵 전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

// 장르 > 재생 횟수 > 고유 번호 순으로 정렬 후 장르 별로 두 개씩 뽑음
// unordered_map으로 각 장르별 재생 횟수 저장
// vector로 정렬? 위 규칙대로 함수 만들어서.

// data 생성
struct music
{
    long long plays; // 재생 횟수
    int i; // 고유 번호
};

unordered_map<string, long long> genresPlays;
unordered_map<string, vector<music>> musics_sorted;

bool cmp(const music& a, const music& b)
{
    if (a.plays == b.plays)
        return a.i < b.i;
    return a.plays > b.plays;
}

vector<int> solution(vector<string> genres, vector<int> plays) 
{
    // 장르별 재생횟수 갱신 
    for (int i = 0; i < genres.size(); i++)
        genresPlays[genres[i]] += plays[i];
    
    // 음악 데이터 저장
    for (int i = 0; i < genres.size(); i++)
    {
        music m;
        m.plays = plays[i];
        m.i = i;
        musics_sorted[genres[i]].push_back(m);
    }

    for (auto& m : musics_sorted)
        sort(m.second.begin(), m.second.end(), cmp);

    // value 값 기준 정렬을 위해 map을 vector로 변환
    vector<pair<string, long long>> genres_sorted(genresPlays.begin(), genresPlays.end());

    // 플레이한 횟수가 많은 장르 별로 정렬
    // 문제 조건에서 모든 장르는 재생된 횟수가 다름.
    sort(genres_sorted.begin(), genres_sorted.end(), [](const pair<string, long long>& a, const pair<string, long long>& b)
        {
            return a.second > b.second;
        });

    vector<int> answer;
    int idx = 0;

    // 정렬된 music에서 장르 별로 최대 두 개씩 뽑음
    for (const auto& genre_pair : genres_sorted) 
    {
        string genre = genre_pair.first;
        
        for(int i = 0; i < min(2, (int)musics_sorted[genre].size()); i++)
            answer.push_back(musics_sorted[genre][i].i);
    }

    return answer;
}

 

🔵 시간 복잡도

for문으로 각 value 값을 정렬 시키는 부분이 제일 시간 복잡도가 크다.

musics_sorted의 길이는 장르의 종류이므로 최대 100이며, algorithm 헤더의 sort는 시간 복잡도가 컨테이너의 길이를 N이라 했을 때 O(NlogN)이다.

musics_sorted의 최대 길이는 100으로 작은 수여서 상수로 취급할 수 있다.

따라서 총 시간 복잡도는 O(NlogN)이다.