[PG] 베스트 앨범 JAVA

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

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

각 노래들의 장르와 플레이 수를 담은 String[] genres, int[] plays가 주어진다.

배열의 인덱스를 각 노래의 고유번호로 한다.

 

이 중 몇 가지 노래를 뽑아 베스트 앨범을 만들고자 한다.

 

베스트 앨범 조건

1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)

2. 장르 별 총 재생 수가 많은 장르부터 뽑는다. 

3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.

4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

 

 

풀이 .

import java.util.*;

//1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)
//2. 장르 별 총 재생 수가 많은 장르부터 뽑는다.
//3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.
//4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

class Song implements Comparable<Song> {
    int index;
    int play;

    public Song() {}
    public Song(int index, int play) {
        this.index = index;
        this.play = play;
    }

    @Override
    public int compareTo(Song o) {
        if (this.play != o.play) {
            if (this.play > o.play) { return -1; }
            else { return 1; }
        } else {
            if (this.index < o.index) { return -1; }
            else { return 1; }
        }
    }
}

class Solution {
    public ArrayList<Integer> solution(String[] genres, int[] plays) {
        // 장르 별 총 재생 수 세기
        Map<String, Integer> jenreHm = new HashMap<String, Integer>();
        for(int i = 0; i < genres.length; i++) {
            String jenre = genres[i];
            if(jenreHm.get(jenre) == null) {
                jenreHm.put(jenre, plays[i]);
            }else {
                jenreHm.put(jenre, jenreHm.get(jenre) + plays[i]);
            }
        }

        // 총 재생 수의 내림차순으로 정렬
        // List에 옮겨 정렬한 후 LinkedHashMap으로 넘겨 순서 유지
        List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>();
        for(Map.Entry<String, Integer> entry : jenreHm.entrySet()) {
            list.add(entry);
        }
        Collections.sort(list, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        Map<String, Integer> sortedJenreHm = new LinkedHashMap<String, Integer>();
        for(Map.Entry<String, Integer> entry : list) {
            sortedJenreHm.put(entry.getKey(), entry.getValue());
        }

        // Map<String, ArrayList<Song>>으로 멀티 맵 구현
        Map<String, ArrayList<Song>> multiHm = new LinkedHashMap<String, ArrayList<Song>>();
        for(String jenre : sortedJenreHm.keySet()) {
            multiHm.put(jenre, new ArrayList<Song>());
        }

        // 장르 별 노래 저장. 이때 장르 별 총 재생 수 내림차순 정렬은 완료되어있음
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            multiHm.get(genre).add(new Song(i, plays[i]));
        }

        // 장르 별 최다 재생 곡 2개 뽑아서 저장
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(ArrayList<Song> aList : multiHm.values()) {
            Collections.sort(aList);
            // 장르에 곡이 하나 뿐이면 하나만 저장
            ansList.add(aList.get(0).index);
            if(aList.size() >= 2) {
                ansList.add(aList.get(1).index);
            }
        }
        return ansList;
    }
}

 

1. 최다 재생 수가 많은 장르부터 수록해야 하므로 hm을 통해 장르 별 총 새생 수 먼저 파악

2. LinkedList를 사용해 총 재생 수로 내림차순 정렬 후 LinkedHashMap으로 옮겨 그 순서를 유지 (그냥 HashMap은 입력 순서 유지되지 않아 정렬이 해쳐짐)

3. 장르 안의 노래들 사이에서도 정렬이 필요. Song 클래스를 만들어 정렬 기준 명시 (play 내림차순, index 오름차순)

4. Map<String, ArrayList<Song>>으로 멀티 맵 구현. 장르 별로 자신의 노래를 저장할 리스트를 갖는다.

5. 각 장르에 해당하는 Song을 모두 담고 이를 내림차순 정렬하여 인덱스 0, 1의 원소(상위 2곡)를 정답 리스트에 저장

 

 

 

너무 주먹구구식의 풀이가 아닌가 싶다. 이정도 방법도 생각하는데 꽤 오랜 시간이 걸렸다.