[프로그래머스 알고리즘 - level3] 베스트 앨범

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

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

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genresplaysreturn

[classic, pop, classic, classic, pop]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

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]번 노래를 그다음에 수록합니다.

 

 

<풀이> 

장르별로 가장 많은 재생횟수를 찾아야 하므로,  장르별로 하나만 저장되면서 재생횟수는 누적할 수 있는 방법은  key 값의 중복을 허용하지 않는 Map을 사용하는게 좋겠다고 생각했다.  처음에는 장르를 키로 갖고, 재생횟수를 값으로 갖는 맵을 생성하려다가..   

문제가 장르별 재생이 가장 많은 순으로 뭔가 일을 해야하므로, 정렬이 필요했고,  그 안에서도 노래별로 정렬이 필요했다.  맵에 값으로 저장되어야 할 정보가 하나가 아니라 여러개이므로 여러가지 자료구조를 사용하는 것보다는 객체를 생성하는게 좋겠다고 생각했다. 

 

장르를 저장할 수 있는 객체를 생성하는데..  장르별 노래의 정보도 따로 알고 있어야 하고, 노래별로도 재생횟수별로 노래의 고유번호를 알고 있어야 했으므로 노래를 저장할 수 있는 객체를 생성하고 장르객체에 노래들을 알고 있으면 좋겠다라는 생각이 든다. 

 

장르별로, 재생횟수가 많은 노래를 2곡씩 결과에 포함시켜야 하는데, 그렇다면 노래도 정렬이 필요해 보인다.  

 

정렬이 되고, 가장 높은순으로 하나씩 꺼내 사용할 수 있는 자료구조로 PriorityQueue 가 존재하는데 가장 알맞아 보였다.  

 

 

장르객체

Genres  

- genres :: String     장르  

- totalPlayCount  : :int    총 재생횟수

- songList : :PriorityQueue  장르별노래들.

 

노래객체 

Song 

- id :: int   고유번호

- playCount :: int  재생횟수

 

- 문제 풀이를 위한 거라서 필드를 패키지영역으로 선언하고, getter/setter생략.  

- 두 객체 모두 정렬이 중요했으므로 정렬의 기준을 삼아줄 Comparable 인터페이스를 구현했다.  

 

package level3;

import java.util.*;
class Song implements Comparable<Song>{
	int id;  //고유번호
    int playCount; //재생횟수
    
    Song(int id, int playCount){
        this.id = id;
        this.playCount = playCount;
    }
    
	//노래별로 재생횟수가 많은 곡을 찾아야 하므로 정렬이 필요하다. 
    @Override
    public int compareTo(Song song) {
    //재생횟수가 같다면, 고유번호가 빠른곡을 수록해야하므로..  
        if(playCount == song.playCount)
            return id - song.id;
        else   //재생횟수가 많은 곡이 먼저 나와야 하므로, - 를 붙혀줌. 
            return -(playCount - song.playCount);
    }
	//테스트용
    public String toString(){
        return id+"";
    }
}
class Genres implements Comparable<Genres>{
    String genres; //장르
    int totalPlayCount; //장르별 총 재생횟수 
    Queue<Song> songList = new PriorityQueue<>(); //장르별 노래. 정렬이 필요해서 우선순위큐 이용
    //생성자
    Genres(String genres){ 
        this.genres = genres;
    }
    //장르객체는 이미 만들어졌지만 해당 장르의 노래가 추가 될때 이용되는 메소드.
    public Genres addSong(Song song){
        this.songList.add(song);
        this.totalPlayCount += song.playCount;
        return this;
    }
    //테스트용
    public String toString(){
        return songList.size()+"::"+totalPlayCount;
    }
	//정렬이 필요하므로 구현, Integer의 compare 이용.
    @Override
    public int compareTo(Genres genres) {
        return -(Integer.compare(this.totalPlayCount, genres.totalPlayCount));
    }
}

public class 베스트앨범 {
    //장르별 재생횟수
    //장르내 재생홧수 많은것,  재생홧수가 같은면 고유번호 낮은 것 먼저 수록
    public static int[] solution(String[] genres, int[] plays) {
        Map<String, Genres> kindMap = new HashMap<>();
        //장르별재생횟수 저장. 장르별로 하나만 저장되야하므로 map의 key는 중복되지 않는점을 이용.
        for(int i = 0; i < genres.length; i++){
        	//key는 장르명을 value는 Genres객체를 넣어줌.  이미 존재하는 장라라면, 기존 장르객체에 노래만 추가해줌. 
            Song song = new Song(i,plays[i]);
            kindMap.put(genres[i], kindMap.getOrDefault(genres[i],new Genres(genres[i])).addSong(song));
        }
		//장르별로 재생횟수가 가장 많은 순으로 작업이 진행되어야 하므로, 우선순위큐 활용. 
        Queue<Genres> queue = new PriorityQueue<>();
        for ( Genres s:kindMap.values()) {
            queue.add(s);
        }

       // 장르별 2곡이 있으라는 보장이 없다.  전체 곡수를 알 수 없음. 그래서 list 사용
        List<Integer> answerList = new ArrayList<Integer>();
        while (!queue.isEmpty()){
        //재생횟수가 가장 많은 장르별로, 하나씩 꺼내서 노래 리스트를 얻어오고, id를 얻어온다. 
            Genres g = queue.poll();
            Queue<Song> songList = g.songList;
            int count=0; //장르별 노래를 2개만 추가할 것이므로 그것을 셀 변수가 필요. 
            while(!songList.isEmpty() && count++ <2){  //노래가 2개 미만일 경우가 있어서.. 
                answerList.add(songList.poll().id);
            }
        }
        //결과값은 배열로 반환해야 하므로, 리스트를 배열로 변환 
        int[] answer = answerList.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }

    public static void main(String[] args) {
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] plays={500, 600, 150, 800, 2500};
        int[] bestAlbum = solution(genres,plays);
        for (int i:bestAlbum
             ) {
            System.out.println(i);
        }
    }
}