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

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

프로그래머스

 

 저는 해시와 우선순위 큐를 이용해 문제를 해결했습니다.

해시를 통해 각 장르의 점수와 장르의 번호를 붙여 저장하였고, 각 장르별로 우선순위 큐를 만들고 가장 큰 값 또는 값이 같다면 번호가 작은 값을 먼저 나오도록 하였습니다.

또, 장르별 점수를 우선순위 큐에 넣고 가장 큰 점수가 먼저 나오게 하여 해당 장르의 우선순위 큐에서 2개씩 꺼내도록 구현하여 문제를 해결하였습니다.

 

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        Map<String,Integer> map = new HashMap<>();
        Map<Integer,Integer> score = new HashMap<>();
        int num = 0;
        

        for(int i = 0 ; i < genres.length ; i++){
            String genre = genres[i];
            int play = plays[i];
            if(!map.containsKey(genre)){
                map.put(genre,num++);
                score.put(map.get(genre),play);
            }else{
                score.merge(map.get(genre),play,(v1,v2)->{
                    return v1+v2;
                });
            }
            
            
        }
        int size = num;
        PriorityQueue<int[]>[] pq = new PriorityQueue[size];
        for(int i = 0 ; i < size ; i++){
            pq[i] = new PriorityQueue<>((v1,v2)->{
                if(v1[1] == v2[1]){
                    return v1[0] - v2[0];
                }
                return v2[1] - v1[1];
            });
        }
        for(int i = 0 ; i < genres.length ; i++){
            int index = map.get(genres[i]);
            pq[index].add(new int[]{i, plays[i]});
        }
        PriorityQueue<int[]> scorePq = new PriorityQueue<>((v1,v2)->{
            return v2[1] - v1[1];
        });
        for(int key : score.keySet()){
            scorePq.add(new int[]{key,score.get(key)});
        }
        List<Integer> list = new LinkedList<>();
        while(!scorePq.isEmpty()){
            int index = scorePq.poll()[0];
            for(int i = 0 ; i < 2; i++){
                if(pq[index].isEmpty()){
                    break;
                }
                list.add(pq[index].poll()[0]);
            }
        }
        System.out.println(list);
        int[] answer = new int[list.size()];
        for(int i = 0 ; i < list.size() ; i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
}