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

문제 링크:
코딩테스트 연습 - 베스트앨범 | 프로그래머스 (programmers.co.kr)

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

 

입출력 예시입니다.

 

• genres, plays 배열의 길이는 같다. (1이상 10000이하)
• i번째 배열의 고유번호는 i이다.
• genres[i]는 고유번호가 i인 노래의 장르, plays[i]는 고유번호가 i인 노래가 재생된 횟수이다.
• 장르의 종류는 100개 미만이다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택한다.
• 모든 장르는 재생된 횟수가 다르다.

 

자바의 HashMap을 활용해보자.

HashMap을 사용하는 이유는?

• 각 장르별로 곡들을 담고, 각 장르별로 총 재생횟수도 알아야 하기 때문이다. 이런식으로 묶는데엔 해시맵이 좋다. 해시맵은 데이터를 저장하고, serach 하는데 좋은 성능을 보인다. 
• genre를 Key값으로, Value 값으로는 곡, 총 재생횟수를 넣을 예정이다.

 

1. 각 장르별 총 재생횟수가 몇인가?

장르별 재생횟수가 많은 순서대로 리턴 배열에 넣어주므로 필요한 정보이다. 장르별 재생횟수를 모두 더한 총 재생횟수를 구해 내림차순으로 정렬하면 될 것이다.

// <genre, 총 재생 횟수>
HashMap<String, Integer> countMap= new HashMap<>();

 

2. 한 장르에 속한 곡당 고유번호와 재생횟수

수록곡에 실을 장르의 순서들을 구했으면, 이제 각 장르에 해당하는 곡들에 대한 정보를 알아야 한다.

한 장르당 2개까지 곡을 고를 수 있고, 이 곡은 재생순서가 많은 순으로 정해진다. 장르 안에서 곡의 재생순서와 고유번호를 담은 배열을 재생순서 내림차순으로 정렬해 위에서부터 고르면 된다.

// <genre, <재생횟수, 고유번호>> , 곡 정보를 담음
HashMap<String, ArrayList<int[]>> map = new HashMap<>();

 

 

3. 해시맵 정렬하기

위에서 언급한 것처럼 내림차순으로 해시맵을 정렬해주어야 하는데, Collections.sort() 를 이용하려면 countMap을 list형태로 바꿔주어야 한다. countMap.entrySet() 을 이용하여 entrySet을 ArrayList로 바꿔준다.

ArrayList<Map.Entry<String, Integer>> entries =
        new ArrayList<Map.Entry<String, Integer>>(countMap.entrySet());

 

소스코드

public int[] solution(String[] genres, int[] plays) {
    int idx= 0;
    int[] ans = new int[201];

    // <genre, <재생횟수, 고유번호>> , 곡 정보를 담음
    HashMap<String, ArrayList<int[]>> map = new HashMap<>();

    // <genre, 총 재생 횟수>
    HashMap<String, Integer> countMap= new HashMap<>();

    for(int i=0;i<genres.length;i++){
        String genre = genres[i];
        ArrayList<int[]> array = map.getOrDefault(genre, new ArrayList<>());
        array.add(new int[]{plays[i], i});
        map.put(genre, array);
    }

    Set<String> keys = map.keySet();
    for (String key : keys) {
        ArrayList<int[]> list = map.get(key);
        for (int[] arr : list) {
            countMap.put(key, countMap.getOrDefault(key, 0)+arr[0]);
        }
    }

    ArrayList<Map.Entry<String, Integer>> entries =
            new ArrayList<Map.Entry<String, Integer>>(countMap.entrySet());

    Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            // 값 내림차순으로 정렬
            return o2.getValue() - o1.getValue();
        }
    });

    for (Map.Entry<String, Integer> entry : entries) {
        String key = entry.getKey();
        // 재생횟수, 고유번호 들어있는 배열
        ArrayList<int[]> values = map.get(key);

        // 재생 횟수 내림차순 정렬
        Collections.sort(values, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if(arr2[0] - arr1[0] > 0) return 1;
                else if(arr2[0] - arr1[0] < 0) return -1;
                else{ // 두 값이 같은 경우 고유번호 값 오름차순
                    return arr1[1] - arr2[1];
                }
            }
        });

        for(int i=0;i<values.size();i++){
            if(i==2) break;
            ans[idx++] = values.get(i)[1];
        }

    }

    int[] ans2 = new int[idx];
    for(int i=0;i<=idx-1;i++){
        ans2[i] = ans[i];
    }
    return ans2;
}