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

programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

 

문제는 위와 같으며, 장르별 노래의 재생 횟수의 합을 저장한 Map과 장르별 노래 리스트를 저장한 Map을 만들어서 정렬함으로써 문제를 해결하였습니다.

 

베스트앨범에 들어갈 노래의 조건을 하나씩 살펴보겠습니다.

 

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

 

이 조건을 확인하기 위해, 주어진 노래를 차례로 확인하면서 장르를 key로 하고 해당 노래가 재생된 횟수의 합을 value로 하여 Map에 저장합니다. 이후 값(value)을 기준으로 내림차순 정렬을 하여 가장 많이 재생된 장르부터 순서대로 노래를 확인할 수 있도록 하였습니다.

 

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

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

 

가장 많이 재생된 장르부터 순서대로 노래 목록을 가져온 뒤, 해당 목록에 포함된 노래들을 재생 횟수를 기준으로 내림차순 정렬합니다. 재생 횟수가 같은 경우에는 먼저 추가된 순서대로 정렬되기 때문에 자동으로 고유 번호가 낮은 노래 순으로 정렬됩니다. 그런다음 최대 2개까지 노래 리스트를 반복하면서 노래의 고유 번호를 정답 리스트에 저장합니다.

 

마지막으로 정답 리스트를 int 배열로 변경하여 반환합니다.

 

Java 코드는 다음과 같습니다.

import java.util.*;

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

        Map<String, Integer> playCountPerGenres = new LinkedHashMap<>();  // 장르별 재생 횟수 합
        Map<String, LinkedList<Song>> songsByGenres = new LinkedHashMap<>();  // 장르별 노래 리스트

        // 주어진 배열을 차례로 확인하면서
        for (int i = 0; i < genres.length; i++) {
            // 장르를 key로 하고 해당 장르의 노래 재생 횟수의 합을 값으로 하여 저장
            playCountPerGenres.put(genres[i], playCountPerGenres.getOrDefault(genres[i], 0) + plays[i]);

            // 장르를 key로 하고 해당 장르의 노래를 리스트로 저장
            Song song = new Song(i, plays[i]);
            LinkedList<Song> tmp = songsByGenres.getOrDefault(genres[i], new LinkedList<>());
            tmp.add(song);
            songsByGenres.put(genres[i], tmp);
        }

        // 재생 횟수를 기준으로 장르를 내림차순 정렬
        Map<String, Integer> sortedPlayCountPerGenres = sortByPlayCount(playCountPerGenres);

        // 가장 많이 재생된 장르별로 차례대로 확인하면서
        for (String key : sortedPlayCountPerGenres.keySet()) {
            // 해당 장르에 속한 노래 리스트를 재생 횟수가 많은 순으로 정렬하여 찾은 뒤
            List<Song> songs = sortByPlays(songsByGenres.get(key));
            // 장르별 최대 2개 노래의 고유 번호를 정답 리스트에 저장
            for (int i = 0; i < songs.size() && i < 2; i++) {
                answer.add(songs.get(i).num);
            }
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }

    // 가장 많이 재생된 장르 순으로 정렬
    private static Map<String, Integer> sortByPlayCount(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> entries = new LinkedList<>(map.entrySet());
        entries.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

        Map<String, Integer> result = new LinkedHashMap<>();
        for (Map.Entry<String, Integer> entry : entries) {
            result.put(entry.getKey(), entry.getValue());
        }

        return result;
    }

    // 한 장르에서 가장 많이 재생된 노래 순으로 정렬
    private static List<Song> sortByPlays(List<Song> list) {
        list.sort(new Comparator<Song>() {
            @Override
            public int compare(Song o1, Song o2) {
                return o2.plays - o1.plays;
            }
        });

        return list;
    }

    // 노래 객체
    private static class Song {
        private final int num;  // 고유 번호 (인덱스)
        private final int plays;  // 재생 횟수

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