프로그래머스 알고리즘 고득점 Kit 해시 - 베스트앨범

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

문제 접근 방식

1. 장르별 총 재생 수를 구한다.
2. 장르별 노래 리스트를 관리한다.
3. 장르를 총 재생 수 기준으로 정렬한다.
4. 각 장르 안에서 노래를 재생 수 기준으로 정렬한 후 상위 2개를 선택한다.

전체 코드

import java.util.*;

class Solution {

    // 각 노래 정보를 저장할 Song 클래스 정의 (인덱스와 재생 수)
    static class Song {
        int idx, plays;

        Song(int idx, int plays) {
            this.idx = idx;
            this.plays = plays;
        }
    }

    public int[] solution(String[] genres, int[] plays) {

        // 장르별 총 재생 수를 저장할 맵
        Map<String, Integer> genreMap = new HashMap<>();

        // 장르별 노래 리스트를 저장할 맵 (Song 객체 리스트)
        Map<String, List<Song>> genreSongMap = new HashMap<>();

        // 1. 장르별 총 재생 수와 장르별 노래 목록을 채움
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];

            // 장르별 총 재생 수 누적
            genreMap.put(genre, genreMap.getOrDefault(genre, 0) + play);

            // 장르별 노래 리스트에 현재 노래 추가
            genreSongMap
                .computeIfAbsent(genre, k -> new ArrayList<>()) // 장르가 없으면 리스트 생성
                .add(new Song(i, play)); // Song 객체 추가
        }

        // 2. 장르를 총 재생 수 기준으로 내림차순 정렬
        List<String> sortedGenres = new ArrayList<>(genreMap.keySet());
        sortedGenres.sort((g1, g2) -> genreMap.get(g2) - genreMap.get(g1));

        // 3. 정답 리스트 생성
        List<Integer> result = new ArrayList<>();

        // 4. 각 장르별로 상위 2곡까지 선택
        for (String genre : sortedGenres) {
            List<Song> songList = genreSongMap.get(genre);

            // 해당 장르의 노래를 정렬: 재생 수 내림차순 → 같으면 인덱스 오름차순
            songList.sort((a, b) -> {
                if (b.plays == a.plays) return a.idx - b.idx;
                return b.plays - a.plays;
            });

            // 상위 2곡까지 정답 리스트에 추가
            for (int i = 0; i < Math.min(2, songList.size()); i++) {
                result.add(songList.get(i).idx);
            }
        }

        // 5. 리스트를 int[] 배열로 변환하여 반환
        return result.stream().mapToInt(i -> i).toArray();
    }
}