베스트-앨범.md

디스크 컨트롤러

문제 링크

문제 설명

장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 만들려고 한다. 규칙은 다음과 같다.

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

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

입출력 예시

Input:
  genres = ["classic", "pop", "classic", "classic", "pop"]
  plays =  [500, 600, 150, 800, 2500]
Output: [4, 1, 3, 0]

문제 풀이

풀이 1
Map을 두개 만든다. 하나는 각 장르별 카운트를 세는 Map {key: 장르이름, value: 장르카운트} 다른 하나는 각 장르별 곡을 담아놓은 PriorityQueue를 값으로 가지는 Map {key: 장르이름, value: 장르별 곡 List(pq)} PriorityQueue의 정렬 기준을 각 곡의 재생 횟수 되도록 한다.

두 개의 Map이 준비 되었다면 카운트Map에 저장된 값들을 장르 카운트 기준으로 정렬 한다. 정렬된 순서대로 각 장르를 순회하면서 해당 장르의 곡들을 정답리스트에 넣는다. 장르별 곡을 저장한 Map에서 map.get(장르이름)하면 정렬된 Queue를 받을 수 있다. 이미 정렬되어 있어서 Queue.poll()로 값을 빼내어 주기만 하면된다. 이 때 한 장르에 2개 초과를 넣을 수 없기 때문에 2개를 넣었다면 break해주는 조건도 넣어주어야 한다.

풀이 2
풀이 1과 크게 다른점은 없다. Map을 하나만 만들고 해당 Map에 카운트 값과 리스트를 가지고 있는 객체를 넣어서 관리하기 편하게 한다.

//map 형태
{   
    key : 장르 이름   
    value : { totalCount: 장르카운트 , musicList: Array[music]  
    *music : {id: i, count: plays[i] }  
}  

풀이 1에서 정렬기준을 카운트로만 줬지만 정확하게 코딩하려면 id도 정렬기준에 포함시키는 이중정렬을 만들어야 한다.

풀이코드 Java & 풀이 1

//고유번호 신경써 주어야함.
import java.util.*;

class Solution {

    public int[] solution(String[] genres, int[] plays) {

        HashMap<String, Integer> countMap = new HashMap<>();
        HashMap<String, PriorityQueue > musicMap = new HashMap<>();

        for(int i = 0 ; i < plays.length ; i++  ){
            countMap.put( genres[i] , countMap.getOrDefault( genres[i] ,0) + plays[i] );
            if(!musicMap.containsKey(genres[i])){
                PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) ->  o2[1] - o1[1] ); //내림차순
                musicMap.put(genres[i],pq);
            }
            int[] arr = new int[] {i,plays[i]};
            musicMap.get(genres[i]).add(arr);
        };

        List<String> sortList = new ArrayList<>(countMap.keySet());
        Collections.sort(sortList, (o1, o2) ->  countMap.get(o2) - countMap.get(o1));

        List<Integer> answerList = new ArrayList<>();
        for(String str : sortList ){
            int count  = 0;
            PriorityQueue<int[]> musicPq = musicMap.get(str);
            while(!musicPq.isEmpty() && count < 2){
                count++;
                int[] arr = musicPq.poll();
                answerList.add(arr[0]);
            }
        }

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

풀이 코드 JavaScript & 풀이 2

// map의 구조 
// key : genre 
// value : { totalCount: Number , musicList: Array[music] }
// *music : {'id':i,'count':plays[i] }
function solution(genres, plays) {

    const map = new Map();
    const len = genres.length;
    for(let i = 0; i < len; i++ ){
        if(!map.has(genres[i])){
            map.set(genres[i],{ totalCount: 0, musicList:[]})
        }           
        map.get(genres[i]).totalCount += plays[i];
        map.get(genres[i]).musicList.push({'id':i,'count':plays[i]});
    }
    let genreInfo = map.values();
    genreInfo = Array.from(genreInfo)
    genreInfo.sort((a, b) =>  b.totalCount - a.totalCount );
    const answer =[];
    for(const { musicList } of genreInfo){
        musicList.sort((a,b) => { 
            if( b.count == a.count) return a.id - b.id;
            else return  b.count - a.count;
        })
        let musicCount = 0;
        for(const {id} of musicList){
            answer.push(id)
            musicCount++;
            if(musicCount  == 2) break;
        }
    }
    return answer;
}