[프로그래머스] Lv.3 : 베스트 앨범 - 자바[Java]

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

풀이

1 <= N <= 10,000 (노래 개수)

 

출력 순서: 속한 노래가 많이 재생된 장르 -> 장르마다 2개의 곡을 선택 (많이 재생된 노래 -> 고유 번호가 작은 순대로)

이 때 장르에 속한 곡이 1곡이라면 1곡만 출력한다.

 

먼저 장르 이름을 key로 하는 HashMap이 필요하다.

value에는 여러가지 값이 필요로 하는데, 각 장르에 포함된 모든 노래 재생 횟수와 각 노래마다 재생 횟수와 고유 번호를 저장해야 한다.

 

이를 위해 class Music과 Genre를 생성했다. Genre에 ArrayList<Music> 멤버를 생성해 각 장르에 속한 노래를 저장하고, 노래를 저장할 때마다 plays를 업데이트한다.

    static class Music implements Comparable<Music> {
        int i; // 고유 번호
        int play; // 재생 횟수
        public Music(int i, int play) {
            this.i = i;
            this.play = play;
        }
        
        @Override
        public int compareTo(Music o) {
            if (this.play == o.play) {
                return this.i - o.i;
            }
            return o.play - this.play;
        }
    }
    
    static class Genre {
        String name; // 이름
        ArrayList<Music> musics = new ArrayList<>(); // 곡 리스트
        int plays = 0; // 속한 노래의 총 재생 횟수
        
        public void addMusic(Music music) {
            musics.add(music);
            plays += music.play;
        }
    }

 

이후 속한 노래가 많이 재생된 장르를 정렬하기 위해 Data라는 임시 클래스를 생성한다.

    static class Data implements Comparable<Data> {
        int sum; // 해당 장르에 속한 모든 노래의 총 재생 횟수
        String name; // 장르 이름
        
        public Data(int sum, String name) {
            this.sum = sum;
            this.name = name;
        }
        
        @Override
        public int compareTo(Data o) {
            return o.sum - this.sum;
        }

 

    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Genre> genreMap = new HashMap<>();
        
        for (int i = 0; i < genres.length; i++) {
            String name = genres[i];
            if (genreMap.containsKey(name)) { // genreMap에 해당 장르가 있다면
                Genre genre = genreMap.get(name);
                genre.addMusic(new Music(i, plays[i]));
            }
            else { // genreMap에 해당 장르가 없다면
                Genre genre = new Genre();
                genre.name = name;
                genre.addMusic(new Music(i, plays[i]));
                genreMap.put(name, genre);
            }
        }
        
        ArrayList<Data> sortData = new ArrayList<>(); // 장르를 정렬하기 위한 임시 자료구조
        for (String key: genreMap.keySet()) {
            Genre genre = genreMap.get(key);
            sortData.add(new Data(genre.plays, genre.name));
        }
        Collections.sort(sortData);
        
        ArrayList<Integer> answerList = new ArrayList<>(); // 정답을 출력하기 위한 임시 자료구조
        for (Data data: sortData) {
            String name = data.name;
            
            Genre genre = genreMap.get(name);
            ArrayList<Music> musics = genre.musics;
            Collections.sort(musics);
            
            answerList.add(musics.get(0).i);
            if (musics.size() > 1) // 장르에 속한 곡이 2개 이상이면, 2번째 곡도 선택한다.
                answerList.add(musics.get(1).i);
        }
        
        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }

 

코드

import java.io.*;
import java.util.*;

class Solution {
    
    static class Music implements Comparable<Music> {
        int i; // 고유 번호
        int play; // 재생 횟수
        public Music(int i, int play) {
            this.i = i;
            this.play = play;
        }
        
        @Override
        public int compareTo(Music o) {
            if (this.play == o.play) {
                return this.i - o.i;
            }
            return o.play - this.play;
        }
    }
    
    static class Genre {
        String name; // 이름
        ArrayList<Music> musics = new ArrayList<>(); // 노래 리스트
        int plays = 0; // 속한 모든 노래의 총 재생 횟수
        
        public void addMusic(Music music) {
            musics.add(music);
            plays += music.play;
        }
    }
    
    static class Data implements Comparable<Data> {
        int sum; // 해당 장르에 속한 모든 노래의 총 재생 횟수
        String name; // 장르 이름
        
        public Data(int sum, String name) {
            this.sum = sum;
            this.name = name;
        }
        
        @Override
        public int compareTo(Data o) {
            return o.sum - this.sum;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Genre> genreMap = new HashMap<>();
        
        for (int i = 0; i < genres.length; i++) {
            String name = genres[i];
            if (genreMap.containsKey(name)) { // genreMap에 해당 장르가 있다면
                Genre genre = genreMap.get(name);
                genre.addMusic(new Music(i, plays[i]));
            }
            else { // genreMap에 해당 장르가 없다면
                Genre genre = new Genre();
                genre.name = name;
                genre.addMusic(new Music(i, plays[i]));
                genreMap.put(name, genre);
            }
        }
        
        ArrayList<Data> sortData = new ArrayList<>(); // 장르를 정렬하기 위한 임시 자료구조
        for (String key: genreMap.keySet()) {
            Genre genre = genreMap.get(key);
            sortData.add(new Data(genre.plays, genre.name));
        }
        Collections.sort(sortData); // 정렬
        
        ArrayList<Integer> answerList = new ArrayList<>(); // 정답을 출력하기 위한 임시 자료구조
        for (Data data: sortData) {
            String name = data.name;
            
            Genre genre = genreMap.get(name);
            ArrayList<Music> musics = genre.musics;
            Collections.sort(musics);
            
            answerList.add(musics.get(0).i);
            
            if (musics.size() > 1) // 장르에 속한 곡이 2개 이상이면, 2번째 곡도 선택한다.
                answerList.add(musics.get(1).i);
        }
        
        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
}