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

문제 링크

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

풀이

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

 

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

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

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

 

먼저, 1번 조건을 충족하기 위해, 각 장르별 재생횟수의 총 합을 구해야 합니다.

HashMap을 활용하여 Key에 장르를, Value에는 해당 장르의 재생횟수를 누적하여 합을 구합니다. 그리고 Value를 기준으로 정렬한 Key(장르)를 배열로 구합니다(코드에서는 sumList). 

 

2번과 3번 조건을 충족하려면 노래를 재생 횟수가 큰 기준으로 정렬하되, 재생 횟수가 같을 경우 Index가 작은 순서대로 정렬해야 합니다.

Key를 Index 번호, Value를 재생 횟수로 하는 키-값 쌍 배열을 만듭니다. 그리고 정렬에 sumList의 장르를 최우선적으로 사용해야 하므로

HashMap 활용하여 Key를 장르, Value에는 방금 만든 배열을 넣습니다(코드에서는 countMap).

 

sumList를 순회하며 각 원소값을 사용해 countMap에서 Value(각 장르별 Index와 재생횟수)를 가져와 새로 생성한 배열에 할당합니다(코드에서는 countList). countList를 재생 횟수(Value)가 큰 순으로 정렬하되 재생횟수가 같을 경우 Index가 작은 순으로 정렬합니다.

 

4번 조건 충족을 위해, countList에서 최대 2곡씩뽑아 answer 배열에 집어넣습니다.

 

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;
    }
}