42579 (해시)

문제 해석

- 아래 조건대로 정렬을 해야 한다. 

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

- classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
-- 고유 번호 3: 800회 재생
-- 고유 번호 0: 500회 재생
-- 고유 번호 2: 150회 재생

- pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
-- 고유 번호 4: 2,500회 재생
-- 고유 번호 1: 600회 재생
- 따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.
- 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

- 즉, [4, 1, 3, 0]이 답이다.

문제 접근 방법

- Hash<String, Integer> genresOfMaxPlays를 통해서 각 genres(노래)마다 play를 모두 더한 값을 저장해준다.

- Hash<String, List<Music>> genresOfPlaysList를 통해서 각 genres(노래)마다 play 횟수를 저장해준다. 

- [정렬] Hash<String, Integer> genresOfMaxPlays을 큰 숫자부터 정렬한다.

- [정렬] Hash<String, List<Music>> genresOfPlaysList를 큰 숫자부터 정렬한다. 

- genresOfMaxPlays의 큰 genres(노래)를 가져와서 genresOfPlaysList.get()을 해준다.
그 다음에 가장 큰 값 2개를 결과 값에 저장해준다.
만약 2개 초과이거나 이하이면 저장할 필요가 없기 때문에 if(i==1) break; 해준다. 

for(Entry<String, Integer> entry : list_entries) {
//            System.out.println(entry.getKey() + " : " + entry.getValue());
    List<Music> playsList = genresOfPlaysList.get(entry.getKey());
    // 원래는 숫자만 있던 것들이 Music로 변경됨
    Collections.sort(playsList, new Comparator<Music>() {
        @Override
        public int compare(Music p1, Music p2) {
            return p2.getX() - p1.getX();
        }
    });

    for(int i=0; i<playsList.size(); i++){
        answerArr.add(playsList.get(i).pos);
        if(i == 1) break;
    }
}

- 마지막으로 answerArr에다가 playList를 담아주어 정답으로 출력해준다. 

answer = new int[answerArr.size()];
for(int i=0; i<answerArr.size(); i++){
    answer[i] = answerArr.get(i);
}

 

헷갈렸던 점

- 런타임 에러가 나서 범위가 문제가 있나 싶었는데, 아무리 봐도 모르겠어서 다른 정답을 봐도 비슷해보였다. 

for문을 줄였을 때에 런타임에러를 해결했다는 글이 있어서 나도 for문을 줄여주니 해결할 수 있었다.

        // 초기화
//        for(int i=0; i<hash.size(); i++){
//            List<Music> list = new ArrayList<>();
//            hashValue.put(genres[i], hashValue.getOrDefault(hashValue.get(i), list));
//        }

- 초기화 부분의 for문을 밑에 for문에서 초기화 하도록 합쳐주었다. 

// 값 저장
for(int i=0; i<length; i++){
    if(genresOfPlaysList.get(genres[i]) == null){
        genresOfPlaysList.put(genres[i], new ArrayList<>());
    }
    List<Music> list = genresOfPlaysList.get(genres[i]);

    // value, index 저장
    Music p = new Music(plays[i], i);
    list.add(p);
    genresOfPlaysList.put(genres[i], list);
}

- Music class에 값을 담아서 정렬하려고 코드를 짤 때에 바로 따다닥 그림이 그려지지는 않아서 천천히 고민하면서 짯다.

전체 코드

package Programmers;

import java.util.Map.Entry;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class PGM_42579 {
    static void print(int[] answer){
        for(int i=0; i<answer.length; i++){
            System.out.print(answer[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] plays = {500, 600, 150, 800, 2500};

//        System.out.println(solution(genres, plays).length);
        print(solution(genres, plays));
//        System.out.println(solution(new String[]{"classic"}, new int[]{500}).length);
        print(solution(new String[]{"classic"}, new int[]{500}));
    }
    static class Music{
        int x;
        int pos;

        public Music(int x, int pos) {
            this.x = x;
            this.pos = pos;
        }

        public int getX() {
            return x;
        }

    }
    public static int[] solution(String[] genres, int[] plays) {
        int length = genres.length;
        int[] answer = {};
        /**
         * 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
         * 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
         * 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
         */
        // 노래의 장르를 나타내는 문자열 배열 genres
        // 노래별 재생 횟수를 나타내는 정수 배열 plays
        HashMap<String, Integer> genresOfMaxPlays = new HashMap<>();
        for(int i=0; i<length; i++){
            if(genresOfMaxPlays.get(genres[i]) == null){
                genresOfMaxPlays.put(genres[i], 0);
            }
            genresOfMaxPlays.put(genres[i], genresOfMaxPlays.get(genres[i]) + plays[i]);

        }

        HashMap<String, List<Music>> genresOfPlaysList = new HashMap<>();
        // 초기화
//        for(int i=0; i<hash.size(); i++){
//            List<Music> list = new ArrayList<>();
//            hashValue.put(genres[i], hashValue.getOrDefault(hashValue.get(i), list));
//        }
        // 값 저장
        for(int i=0; i<length; i++){
            if(genresOfPlaysList.get(genres[i]) == null){
                genresOfPlaysList.put(genres[i], new ArrayList<>());
            }
            List<Music> list = genresOfPlaysList.get(genres[i]);

            // value, index 저장
            Music p = new Music(plays[i], i);
            list.add(p);
            genresOfPlaysList.put(genres[i], list);
        }

        // hash 내림차순으로 정렬
        List<Entry<String, Integer>> list_entries
                = new ArrayList<Entry<String, Integer>>(genresOfMaxPlays.entrySet());
        Collections.sort(list_entries, new Comparator<Entry<String, Integer>>() {
            // compare로 값을 비교
            public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2)
            {
                // 내림 차순으로 정렬
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });

        ArrayList<Integer> answerArr = new ArrayList<>();
        // 결과 출력
        for(Entry<String, Integer> entry : list_entries) {
//            System.out.println(entry.getKey() + " : " + entry.getValue());
            List<Music> playsList = genresOfPlaysList.get(entry.getKey());
            // 원래는 숫자만 있던 것들이 Music로 변경됨
            Collections.sort(playsList, new Comparator<Music>() {
                @Override
                public int compare(Music p1, Music p2) {
                    return p2.getX() - p1.getX();
                }
            });

            for(int i=0; i<playsList.size(); i++){
                answerArr.add(playsList.get(i).pos);
                if(i == 1) break;
            }
        }

        answer = new int[answerArr.size()];
        for(int i=0; i<answerArr.size(); i++){
            answer[i] = answerArr.get(i);
        }

        return answer;
    }
}