문제

Programmers, 베스트앨범

핵심

• genres, plays의 배열 길이가 각각 10000이므로, 시간복잡도 $O(N^2)$미만 알고리즘을 사용한다.
• 장르별로 가장 많이 재생된 노래를 2개씩 모아 베스트 앨범을 만든다. 노래를 수록하는 기준이 있는데 이를 효율적으로 처리하기 위해서 어떤 자료구조에 어떤 데이터를 담을지가 가장 중요하다고 생각한다.
• 문제를 해결하기 위해선 첫째로 가장 많이 재생된 장르를 알아야 한다. 장르를 key, playtime 합계를 value로 하여 해시 자료구조를 만들고 이를 배열로 변환한 뒤 정렬을 수행하면 가장 많이 재생된 장르 순서를 알 수 있다.
• 둘째로는 어떤 장르에 대해서 가장 많이 재생된 노래를 알아야 한다. 재생 횟수가 같다면 id는 낮은 순으로 정렬해야 한다. 이를 효율적으로 수행하기 위해 장르를 key값으로 하는 노래 배열(노래 배열에는 id와 playtime)을 value로 하여 정렬 함수를 이용해 문제에 요구사항에 맞게 정렬한다.

개선

• Java Map 인터페이스에서 computeIfAbsent()를 활용하면 키가 없거나 null일 때의 동작을 처리할 수 있어 코드가 간결해진다.

if (!songs.containsKey(genres.get(i)))
	songs.put(genres.get(i), new ArrayList<>());
songs.get(genres.get(i)).add(new int[]{i, plays.get(i)});

 songs.computeIfAbsent(genres[i], k -> new ArrayList<>()).add(new int[]{i, plays[i]});

코드

시간복잡도

• O($L \times log_2L)$
• 장르의 종류가 100미만이므로, 노래를 정렬하는 시간복잡도를 기준으로 계산한다.

C++

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    unordered_map<string, int> popularGenres;
    unordered_map<string, vector<pair<int, int>>> songs;
    for (int i = 0; i < genres.size(); ++i) {
        popularGenres[genres[i]] += plays[i];
        songs[genres[i]].push_back({i, plays[i]});
    }
    vector<pair<string, int>> popularGenresVec(popularGenres.begin(), popularGenres.end());
    sort(popularGenresVec.begin(), popularGenresVec.end(), [](auto& a, auto& b) {
       return a.second > b.second; 
    });
    for (auto& song : songs) {
        sort(song.second.begin(), song.second.end(), [](auto& a, auto &b) {
            if (a.second == b.second)
                return a.first < b.first;
            return a.second > b.second;
        });
    }
    vector<int> answer;
    for (auto& genre : popularGenresVec) {
        int jdx = 0;
        for (auto &p : songs[genre.first]) {
            if (jdx >= 2) break;
            answer.push_back(p.first);
            ++jdx;
        }
    }
    return answer;
}

Java

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> popularGenres = new HashMap<>();
        HashMap<String, ArrayList<int[]>> songs = new HashMap<>();
        for (int i = 0; i < genres.length; ++i) {
            popularGenres.put(genres[i], popularGenres.getOrDefault(genres[i], 0) + plays[i]);
            songs.computeIfAbsent(genres[i], k -> new ArrayList<>()).add(new int[]{i, plays[i]});
        }
        var popularGenresList = new ArrayList<>(popularGenres.entrySet());
        popularGenresList.sort((a, b) -> b.getValue().compareTo(a.getValue()));
        for (var song : songs.values()) {
            song.sort((a, b) -> {
                if (a[1] == b[1])
                    return Integer.compare(a[0], b[0]);
                return Integer.compare(b[1], a[1]);
            });
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (var genre : popularGenresList) {
            int jdx = 0;
            for (var song : songs.get(genre.getKey())) {
                if (jdx >= 2) break;
                ans.add(song[0]);
                ++jdx;
            }
        }
        int[] answer = new int[ans.size()];
        int idx = 0;
        for (var e : ans)
            answer[idx++] = e;
        return answer;
    }
}