[Java][프로그래머스][알고리즘 고득점 Kit][Level 3] 베스트앨범

1. 문제 정보

 

2. 도입부 

스트리밍 사이트에서 가장 많이 재생된 곡들을 장르별로 추출하여 '베스트 앨범'을 만드는 시나리오는 실무에서도 흔히 접할 수 있는 데이터 가공 요구사항이다. 단순히 전체 리스트를 정렬하는 것이 아니라, '장르'라는 카테고리로 묶고, 그 안에서 다시 '재생 횟수'와 '고유 번호'라는 다중 기준을 적용해야 한다. 이 과정에서 어떤 자료구조를 선택해 데이터를 그룹화할 것인지, 그리고 자바의 정렬 인터페이스를 어떻게 활용할 것인지가 이 문제의 핵심이다. 특히 HashMap이라는 편리한 도구를 쓰면서도 왜 굳이 별도의 List를 만들어야 했는지, 그 기술적 배경을 중심으로 정리해 본다.

 

3. 주요 특징 및 핵심 로직

이 문제의 요구사항은 크게 세 가지 우선순위로 나뉜다. 이를 해결하기 위해 데이터를 두 가지 관점에서 관리해야 한다.

1. 장르별 총 재생 횟수 관리: 어떤 장르를 먼저 수록할지 결정하기 위해 필요하다.
2. 장르 내 곡 정보 관리: 장르 안에서 어떤 곡이 더 많이 재생되었는지, 혹은 고유 번호가 낮은지 비교하기 위해 필요하다.

구조 설명: 입력 데이터(genres, plays)가 들어오면 Map<장르, 총 재생수>와 Map<장르, 곡 리스트>로 분리되어 저장된다. 이후 장르 맵을 기준으로 내림차순 정렬을 수행하고, 정렬된 장르 순서대로 곡 리스트 맵에 접근하여 곡 단위 정렬 및 상위 2개 추출을 진행한다.

4. 상세 가이드 및 심층 분석

🔍 STEP 1. 데이터 그룹화 (Mapping)

먼저 각 노래의 정보를 적절한 자료구조에 담아야 한다. 장르별 총 합계를 위한 genre 맵과, 장르별 곡 상세 정보(int[]{고유번호, 재생수})를 담을 list 맵을 사용한다.

• genre Map: Key(장르명) - Value(총 재생합)
• list Map: Key(장르명) - Value(List<int[]>)

🔍 STEP 2. 장르 우선순위 결정 (Map을 List로 변환하는 이유)

가장 많이 재생된 장르를 찾기 위해 genre 맵을 사용하지만, 여기서 중요한 기술적 포인트가 등장한다. "왜 Map을 그대로 쓰지 않고 List를 따로 선언했는가?" 에 대한 답이다.

1. HashMap은 순서를 보장하지 않는다: HashMap은 데이터를 빠르게 찾기 위한 용도이지, 순서를 유지하거나 특정 기준(Value)으로 데이터를 줄 세우는 데 최적화되어 있지 않다.
2. Value 기준 정렬의 한계: Map 인터페이스 자체에는 Value를 기준으로 Key들을 정렬하는 메서드가 없다. 따라서 정렬이 가능한 List 자료구조로 Key값(keySet())들을 옮겨 담아야 한다.
3. Comparator 활용: List로 옮긴 뒤에야 비로소 genre.get(key)를 호출하여 총 재생수를 비교하는 커스텀 정렬 로직을 적용할 수 있게 된다.

🔍 STEP 3. 장르 내 곡 정렬 및 추출

정렬된 장르 리스트를 순회하며 각 장르에 속한 곡들을 꺼낸다. 이때 문제에서 제시한 복합 정렬 조건을 적용한다.

• 조건 1: 재생 횟수 내림차순 (b[1] - a[1])
• 조건 2: 재생 횟수가 같으면 고유 번호 오름차순 (a[0] - b[0])

정렬된 결과에서 최대 2개의 곡만 선택하여 최종 결과 리스트에 추가한다.

5. 구현 코드 (Java)

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 장르별 총 재생 횟수를 저장하는 맵
        Map<String, Integer> genreMap = new HashMap<>();
        // 장르별 노래 리스트(고유번호, 재생수)를 저장하는 맵
        Map<String, List<int[]>> listMap = new HashMap<>();
        
        // 1. 데이터를 순회하며 맵에 정보 저장
        for(int i = 0; i < genres.length; i++){
            genreMap.put(genres[i], genreMap.getOrDefault(genres[i], 0) + plays[i]);
            
            listMap.putIfAbsent(genres[i], new ArrayList<>());
            listMap.get(genres[i]).add(new int[]{i, plays[i]});
        }
        
        // 2. [중요] Map의 Key들을 List로 변환하여 정렬 준비
        // Map 자체는 정렬 기능을 제공하지 않으므로 List에 담아 Comparator를 사용한다.
        List<String> genreList = new ArrayList<>(genreMap.keySet());
        genreList.sort((a, b) -> genreMap.get(b) - genreMap.get(a));
        
        List<Integer> result = new ArrayList<>();
        
        // 3. 정렬된 장르 순서대로 처리
        for(String s : genreList){
            List<int[]> songs = listMap.get(s);
            
            // 장르 내 곡 정렬 (재생수 내림차순 -> 고유번호 오름차순)
            songs.sort((a, b) -> {
                if(b[1] == a[1]) return a[0] - b[0];
                return b[1] - a[1];
            });
            
            // 상위 최대 2곡 추출
            result.add(songs.get(0)[0]);
            if(songs.size() > 1){
                result.add(songs.get(1)[0]);
            }
        }
        
        // 4. 결과 반환
        return result.stream().mapToInt(i -> i).toArray();
    }
}