프로그래머스 | 베스트앨범 (Java)

🔒문제

프로그래머스 Lv.3 해시 베스트 앨범

🔑해결

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return하는 solution 함수를 작성하는 문제이다.

HashMap을 사용하여 장르별, 노래별 재생 횟수를 계산하고
PriorityQueue를 사용해 내림차순 정렬을 해주었다.

🔓코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genre_list = new HashMap<>(); // 장르별 재생횟수
        HashMap<String, PriorityQueue<Song>> song_list = new HashMap<>(); // 장르별 노래와 노래의 재생횟수

        for (int i = 0; i < genres.length; i++) {
            if (!song_list.containsKey(genres[i])) {
                PriorityQueue<Song> pq = new PriorityQueue<>();
                song_list.put(genres[i], pq);
                genre_list.put(genres[i], 0);
            }

            song_list.get(genres[i]).add(new Song(i, plays[i]));
            genre_list.put(genres[i], genre_list.get(genres[i]) + plays[i]);
        }

        PriorityQueue<Genre> sort_genre = new PriorityQueue<>();
        for (String key : genre_list.keySet()) {
            sort_genre.add(new Genre(key, genre_list.get(key)));
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (!sort_genre.isEmpty()) {
            Genre gen = sort_genre.poll();
            PriorityQueue<Song> pq = song_list.get(gen.gen);
            for (int i = 0; i < 2; i++) {
            // 장르 별로 가장 많이 재생된 노래 2 개씩 수록
                if (pq.isEmpty())
                    break;
                list.add(pq.poll().num);
            }
        }

        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}
class Genre implements Comparable<Genre> {
    String gen;
    int plays;

    public Genre(String genre, int plays) {
        this.gen = genre;
        this.plays = plays;
    }

    @Override
    public int compareTo(Genre o) {
        return (this.plays > o.plays) ? -1 : 1;
    }
}

class Song implements Comparable<Song> {
    int num;
    int plays;

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

    @Override
    public int compareTo(Song o) {
    	// 내림차순 정렬
        if (this.plays > o.plays) {
            return -1;
        } else if (this.plays == o.plays) {
        	// 장르 내에서 재생 횟수가 같으면
            // 고유 번호가 낮은 노래 먼저 수록
            return this.num - o.num;
        } else {
            return 1;
        }
    }
}