[PCCP] Lv3: 베스트 앨범(42579) 해설

문제

- 문제 링크: 베스트 앨범

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: play와 genres의 길이

- G: 장르의 수

- 각 노래의 장르와 재생 횟수를 맵에 저장하는 시간 복잡도: O(N)

- 장르별 총 재생 횟수를 기준으로 정렬하기 위한 시간 복잡도는 O(GlogG)이미만 G는 최대 100이므로 상수로 고려 가능

- 각 장르 내에서 노래를 재생 횟수순으로 정렬하기 위한 시간 복잡도: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

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

using namespace std;

bool compareGenre(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second > b.second;
}

bool compareSong(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, vector<pair<int, int>>> genres_dict;
    unordered_map<string, int> play_dict;
    
    // 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
    for (int i = 0; i < genres.size(); ++i) {
        genres_dict[genres[i]].push_back({i, plays[i]});
        play_dict[genres[i]] += plays[i];
    }
    
    // 총 재생 횟수가 많은 장르순으로 정렬
    vector<pair<string, int>> sorted_genres(play_dict.begin(), play_dict.end());
    sort(sorted_genres.begin(), sorted_genres.end(), compareGenre);
    
    // 각 장르 내에서 노래를 재생 횟수순으로 정렬해 최대 2곡까지 선택
    for (auto& genre : sorted_genres) {
        auto& songs = genres_dict[genre.first];
        sort(songs.begin(), songs.end(), compareSong);
        
        for (int i = 0; i < min(2, (int)songs.size()); ++i) {
            answer.push_back(songs[i].first);
        }
    }
    return answer;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: play와 genres의 길이

- G: 장르의 수

- 각 노래의 장르와 재생 횟수를 해시맵에 저장: O(N)

- 장르별 총 재생 횟수를 기준으로 정렬: O(GlogG)

- G는 최대 100이므로 상수로 고려하고 무시

- 각 장르 내에서 노래를 재생 횟수 순으로 정렬: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Stream;

public class Solution {

    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, ArrayList<int[]>> genreMap = new HashMap<>();
        HashMap<String, Integer> playMap = new HashMap<>();

        // 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];
            if (!genreMap.containsKey(genre)) {
                genreMap.put(genre, new ArrayList<>());
                playMap.put(genre, 0);
            }
            genreMap.get(genre).add(new int[]{i, play});
            playMap.put(genre, playMap.get(genre) + play);
        }

        ArrayList<Integer> answer = new ArrayList<>();

        // 총 재생 횟수가 많은 장르순으로 내림차순 정렬
        Stream<Map.Entry<String, Integer>> sortedGenre = playMap.entrySet()
                                                                .stream()
                                                                .sorted((o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));

        // 각 장르 내에서 노래를 재생 횟수 순으로 정렬해 최대 2곡까지 선택
        sortedGenre.forEach(entry -> {
            Stream<int[]> sortedSongs = genreMap.get(entry.getKey()).stream()
                                                                    .sorted((o1, o2) -> Integer.compare(o2[1], o1[1]))
                                                                    .limit(2);
            sortedSongs.forEach(song -> answer.add(song[0]));
        });

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

}

solution 2)

#include<>

 

(Python)

solution 1)

- N: plays와 genres의 길이

- G: 장르의 수

- 각 노래의 장르와 재생 횟수를 딕셔너리에 저장: O(N)

- 장르별 총 재생 횟수를 기준으로 정렬하기 위한 시간 복잡도: O(GlogG)

- G는 최대 100이므로 상수로 고려하여 무시

- 각 장르 내에서 노래를 재생 횟수 순으로 정렬: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

def solution(genres, plays):
    answer = []
    genres_dict = {}
    play_dict = {}
    
    # 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
    for i in range(len(genres)):
        genre = genres[i]
        play = plays[i]
        if genre not in genres_dict:
            genres_dict[genre] = []
            play_dict[genre] = 0
        genres_dict[genre].append((i, play))
        play_dict[genre] += play
        
    # 총 재생 횟수가 많은 장르순 정렬
    sorted_genres = sorted(play_dict.items(), key=lambda x: x[1], reverse=True)
    
    # 각 장르 내에서 노래를 재생 횟수 순으로 정렬해 최대 2곡까지 선택
    for genre, _ in sorted_genres:
        sorted_songs = sorted(genres_dict[genre], key=lambda x: (-x[1], x[0]))
        answer.extend([idx for idx, _ in sorted_songs[:2]])
        
    return answer

solution 2)

import

 

(JavaScript)

solution 1)

- N: plays와 genres의 길이

- G: 장르의 수

- 각 노래의 장르와 재생 횟수를 오브젝트에 저장: O(N)

- 장르별 총 재생 횟수를 기준으로 정렬: O(GlogG). G는 최대 100이므로 상수로 고려하고 무시

- 각 장르 내에서 노래를 재생 횟수 순으로 정렬: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

function solution(genres, plays) {
    let answer = [];
    const genresObj = {};
    const playObj = {};
    
    // 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
    for (let i = 0; i < genres.length; ++i) {
        genre = genres[i];
        play = plays[i];
        
        if (!(genre in genresObj)) {
            genresObj[genre] = [];
            playObj[genre] = 0;
        }
        
        genresObj[genre].push([i, play]);
        playObj[genre] += play;
    }
    
    // 총 재생 횟수가 많은 장르순으로 정렬
    sortedGenres = Object.keys(playObj).sort((a, b) => {
        return playObj[b] - playObj[a];
    });
    
    // 각 장르 내에서 노래를 재싱 횟수 순으로 정렬해 최대 2곡까지 선택
    for (const genre of sortedGenres) {
        sortedSongs = genresObj[genre].sort((a, b) => {
            return a[1] === b[1] ? a[0] - b[0] : b[1] - a[1];
        });
        
        answer.push(...sortedSongs.slice(0, 2).map((song) => song[0]));
    }
    
    return answer;
}

solution 2)

import