[Programmers] 베스트앨범

[Level 3] 베스트앨범

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

• 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려한다.
• 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같다.
• 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
• 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
• 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
• 노래의 장르를 나타내는 genres[]와 노래별 재생 횟수를 나타내는 plays[]가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하시오. 

 

 

Solution

• HashMap의 key는 장르이름, value로는 genreList의 index를 가짐
• Genre 마다 내부적으로 리스트를 만들어 같은 Genre의 노래를 저장하고, 우선순위를 위한 totalPc 변수도 생성
• GenreList를 totalPc를 기준으로 내림차순으로 정렬하고, list에서 두 개씩 뽑아 playList에 추가

 

 

소스코드

import java.io.IOException;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
 
public class Solution {
    static Map<String, Integer> map;
    static List<Genre> genreList;
    static List<Integer> playList;
    static int[] answers;
 
    static class Song implements Comparable<Song> {
        private int id;
        private int pc;
 
        public Song(int id, int pc) {
            this.id = id;
            this.pc = pc;
        }
 
        @Override
        public int compareTo(Song o) {
            return (o.pc > this.pc) ? 1 : (o.pc == this.pc) ? (this.id - o.id) : -1;
        }
    }
 
    static class Genre implements Comparable<Genre> {
        private String name;
        private int count = 0;
        private int totalPc = 0;
        private List<Song> list;
 
        public Genre(String name, int count, int id) {
            list = new LinkedList<>();
            this.name = name;
            addSong(id, count);
        }
 
        public void addSong(int id, int pc) {
            list.add(new Song(id, pc));
            this.totalPc += pc;
            this.count++;
        }
 
        @Override
        public int compareTo(Genre o) {
            return o.totalPc - this.totalPc;
        }
    }
 
    static int[] solution(String[] genres, int[] plays) {
        init();
        int index = 0;
        for (int i = 0; i < genres.length; i++) {
            if (map.containsKey(genres[i])) {
                genreList.get(map.get(genres[i])).addSong(i, plays[i]);
            } else {
                map.put(genres[i], index);
                genreList.add(new Genre(genres[i], plays[i], i));
                index++;
            }
        }
        Collections.sort(genreList);
        addPlayList();
        return answers;
    }
 
    static void addPlayList() {
        for (Genre g : genreList) {
            Collections.sort(g.list);
            int count = 0;
            while (count < 2) {
                playList.add(g.list.get(count).id);
                count++;
                if (g.count < 2) {
                    break;
                }
            }
        }
        answers = new int[playList.size()];
        for (int i = 0; i < playList.size(); i++) {
            answers[i] = playList.get(i);
        }
    }
 
    static void init() {
        map = new HashMap<>();
        genreList = new LinkedList<>();
        playList = new LinkedList<>();
    }
}