프로그래머스 42579 베스트앨범 (Java)

문제 링크

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

풀이

본질은 정렬 문제로 알고리즘 자체는 어렵지 않지만, 지켜야 할 조건이 많아 다소 난해한 문제입니다.

 

문제에서 요구하는 수록 조건은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
4. 장르마다 노래는 최대 2곡까지만 수록한다.

정리하면, 각 노래에 고유 인덱스를 부여한 뒤 위 규칙대로 정렬하고, 그 순서대로 인덱스를 출력하면 되는 문제입니다.

풀이는 장르를 정렬하고(조건 1) → 각 장르 안에서 노래를 정렬한 뒤(조건 2·3) → 장르별로 2곡씩만 골라 담는(조건 4) 흐름으로 진행됩니다.

 

1.  장르 정렬 (조건 1)

먼저 장르별 재생 횟수의 총합이 필요합니다. HashMap의 Key에 장르, Value에 누적 재생 횟수를 저장하면 한 번의 순회로 총합을 구할 수 있습니다. 이렇게 만든 맵을 Value(재생 횟수 합) 기준으로 내림차순 정렬한 뒤, 그 순서대로 장르(Key)만 뽑아 배열로 만듭니다. 코드에서는 이 배열을 sumList라고 부릅니다.

 

2.  장르별 노래 정렬 (조건 2·3)

이번에는 각 노래를 (인덱스, 재생 횟수) 쌍으로 다룹니다. 노래를 장르별로 묶어야 하므로, HashMap의 Key에 장르, Value에 그 장르에 속한 (인덱스, 재생 횟수) 쌍들의 배열을 저장합니다. 코드에서는 이 맵을 countMap이라고 부릅니다.

이제 sumList를 순서대로 순회합니다. 각 장르를 Key로 countMap에서 해당 장르의 노래 배열을 꺼내(countList), 재생 횟수 내림차순으로 정렬하되 재생 횟수가 같으면 인덱스 오름차순으로 정렬합니다. 이렇게 하면 조건 2와 3이 동시에 충족됩니다.

 

 

3. 장르별 2곡 선별 (조건 4)

정렬된 countList에서 앞에서부터 최대 2곡의 인덱스를 꺼내 answer 배열에 담습니다.(Math.min 메서드 사용)

sumList 순회가 끝나면 answer 배열에는 최종 수록 순서대로 인덱스가 담겨 있습니다. 이 배열을 출력하면 문제의 답이 됩니다.

코드

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> solution(String[] genres, int[] plays) {
        Map<String, Integer> sum = new HashMap<>();
        Map<String, List<int[]>> list = new HashMap<>();
        
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int count = plays[i];
            sum.put(genre, sum.getOrDefault(genre, 0) + count);
            list.computeIfAbsent(genre, 
            	k -> new ArrayList<>()).add(new int[]{i, count});
        }
        
        List<String> sumList = new ArrayList<>(sum.keySet());
        sumList.sort((a, b) -> {
            return sum.get(b) - sum.get(a);
        });
        
        List<Integer> answer = new ArrayList<>();
        
        for (String genre : sumList) {
            List<int[]> countList = list.get(genre);
            countList.sort((a, b) -> {
                if (a[1] == b[1]) {
                    return a[0] - b[0];
                }
                return b[1] - a[1];
            });
        
            for (int i = 0; i < Math.min(countList.size(), 2); i++) {
                answer.add(countList.get(i)[0]);
            }
        }
        
        return answer;
    }
}