[프로그래머스] 42579. 베스트 앨범

문제 링크

[프로그래머스] 42579. 베스트 앨범

풀이 과정

HashMap 자료 구조를 사용해 문제를 해결했습니다. key 는 장르, value 는 해당 장르의 곡들 정보가 들어갑니다. 문제에 주어진 앨범에 노래를 수록하는 기준을 따르기 위해, 곡들의 정보를 저장하기 위해 Info 라는 클래스를 만들었으며, 이 클래스에는 해당 장르가 몇 번 재생 되었는 지 총 횟수인 sum 과, 각 노래의 고유 번호 및 재생 횟수를 갖고 있기 위한 list 가 있습니다.

아래 문제에서 주어진 입력 예시를 통해 알아보겠습니다.

각 곡들의 장르와 재생 횟수가 주어진 배열을 갖고, 위에서 제가 생각한 구조로 아래와 같은 HashMap 을 구성했습니다.

이제 이 자료구조로 문제에서 주어진 아래의 조건에 따라 정렬을 합니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

4. 장르의 총 재생 횟수를 기준으로 정렬합니다.

   

   HashMap 은 자체적인 정렬 함수를 제공하지 않기 때문에, keyset을 가져와 ArrayList를 생성하고, 이 리스트를 정렬합니다.

5. 이제, 재생 횟수 기준 내림차순으로 정렬된 장르 내에서 각 곡들의 재생 횟수를 기준으로 내림차순 정렬합니다.

   

   HashMap 각각의 entry는 장르와, 장르에 속하는 곡들의 정보 쌍으로 이루어져 있습니다. entry를 돌며, list를 재생 횟수 기준 내림차순으로 정렬합니다.

6. 장르 별로 재생 횟수가 높은 두 개의 노래의 인덱스를 최종 answer 리스트에 저장합니다.

   

코드

import java.util.*;

public class Main {
    public static ArrayList<Integer> solution(String[] genres, int[] plays) {
        ArrayList<Integer> answer = new ArrayList<>();

        Map<String, Info> hashMap = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            if (!hashMap.containsKey(genres[i])) {
                ArrayList<int[]> tmp = new ArrayList<>();
                tmp.add(new int[]{plays[i], i});
                Info info = new Info(plays[i], tmp);

                hashMap.put(genres[i], info);
            } else {
                Info info = hashMap.get(genres[i]);
                info.sum += plays[i];
                info.list.add(new int[]{plays[i], i});

                hashMap.put(genres[i], info);
            }
        }

        // 각 장르의 총 재생 횟수를 기준으로 내림차순 정렬합니다.
        ArrayList<String> keyList = new ArrayList<>(hashMap.keySet());
        Collections.sort(keyList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return hashMap.get(o2).sum - hashMap.get(o1).sum;
            }
        });

        // 각 장르별 재생 횟수를 기준으로 내림차순 정렬합니다.
        for (Map.Entry entry : hashMap.entrySet()) {
            Info info = (Info) entry.getValue();

            Collections.sort(info.list, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[0] - o1[0];
                }
            });
        }

        // 장르 별로 재생 횟수가 높은 두 개(곡이 한 개라면 하나만)의 노래의 인덱스를 리스트에 저장합니다.
        for (String key : keyList) {
            ArrayList<int[]> list = hashMap.get(key).list;

            answer.add(list.get(0)[1]);

            if (list.size() >= 2)
                answer.add(list.get(1)[1]);
        }

        return answer;
    }

    static class Info {
        int sum;
        ArrayList<int[]> list;

        public Info(int sum, ArrayList<int[]> list) {
            this.sum = sum;
            this.list = list;
        }
    }

    public static void main(String[] args) {
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] playes = {500, 600, 150, 800, 2500};

        solution(genres, playes);
    }
}