프로그래머스 베스트앨범 자바 풀이

문제 링크

문제 풀이 시간 :

문제 요약

장르별로 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시
많이 재생된 장르부터, 장르 내에서는 재생 횟수가 많은 노래부터 수록
재생 횟수가 같으면 고유 번호가 낮은 노래를 먼저 수록
genres, plays의 길이는 1 이상 10,000 이하, 장르 종류는 100개 미만

문제 풀이

처음엔 노래 배열을 한 번 순회해서 장르별로 리스트에 다 모은 다음, 각 리스트를 재생 횟수 내림차순으로, 장르 리스트는 총 재생 횟수 내림차순으로 각각 정렬해서 순서대로 상위 2곡씩 뽑으면 되겠다고 생각했다.

하지만 이렇게 하면 리스트를 다 채운 뒤에 매번 새로 정렬해야 하고, "재생 횟수가 같으면 고유 번호가 낮은 노래가 먼저"라는 조건까지 Comparator에 같이 넣어야 해서 정렬 기준이 지저분해진다.

이 문제의 핵심은 노래를 하나씩 읽어 들이면서 바로 우선순위 큐에 넣어 정렬 상태를 유지하면, 다 읽고 나서 따로 정렬할 필요가 없다는 점이다.

장르마다 PriorityQueue<Music>을 하나씩 두고, 재생 횟수가 많으면 먼저, 같으면 고유 번호가 작은 게 먼저 나오도록 비교자를 만든다.
장르별 총 재생 횟수는 HashMap<String, Genre>에 누적하면서, 장르 전체를 담당하는 PriorityQueue<Genre>에도 넣어 총 재생 횟수 내림차순으로 꺼낼 수 있게 한다.
장르 큐에서 하나씩 꺼내면서 그 장르의 노래 큐에서 최대 2개까지 고유 번호를 뽑아 답에 추가한다.

최종 코드

java

import java.util.*;

class Genre{
    public int idx;
    public int cnt;
    
    public Genre(int idx, int cnt){
        this.idx = idx;
        this.cnt = cnt;
    }
}

class Music{
    public int idx;
    public int cnt;
    
    public Music(int idx, int cnt){
        this.idx = idx;
        this.cnt = cnt;
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        int len = genres.length;
        HashMap<String, Genre> map = new HashMap<>();
        
        ArrayList<PriorityQueue<Music>> arr = new ArrayList<>();
        
        int arrIdx = 0;
        for(int i=0;i<len;i++){
            if(map.containsKey(genres[i])){
                Genre now = map.get(genres[i]);
                now.cnt += plays[i];
                
                arr.get(now.idx).add(new Music(i,plays[i]));
            }
            else{
                map.put(genres[i], new Genre(arrIdx, plays[i]));
                arr.add(new PriorityQueue<Music>((o1,o2)->{
                    if(o1.cnt == o2.cnt) return o1.idx - o2.idx;
                    return o2.cnt - o1.cnt;
                }));
                arr.get(arrIdx++).add(new Music(i,plays[i]));
            }
            
            // Genre now = map.get(genres[i]);
            // System.out.println(now.idx);
            // Music[] m = arr.get(now.idx).toArray(new Music[0]);
            // for(int j=0;j<arr.get(now.idx).size();j++){
            //     System.out.print(m[j].idx+" ");
            // }
            // System.out.println();
        }
        
        PriorityQueue<Genre> pq = new PriorityQueue<>((o1, o2)->o2.cnt - o1.cnt);
        
        for(String key:map.keySet()){
            pq.add(map.get(key));
        }
        
        ArrayList<Integer> ans = new ArrayList<>();
        
        while(!pq.isEmpty()){
            Genre now = pq.poll();
            PriorityQueue<Music> musics = arr.get(now.idx);
            // System.out.println(now.idx);
            for(int j=0;j<2;j++){
                if(musics.isEmpty())
                    break;
                // System.out.println(musics.peek().idx + " "+ musics.peek().cnt);
                ans.add(musics.poll().idx);
            }
        }
        
        answer = new int[ans.size()];
        for(int i=0;i<ans.size();i++){
            answer[i] = ans.get(i);
        }
        return answer;
    }
}

/*
Music 클래스 (인덱스, 재생 횟수)
장르별로 우선순위큐 생성, Music 클래스로 넣음 배열로 저장
재생 횟수로 정렬
장르 별 전체 재생횟수
*/

베스트앨범

문제 풀이 시간 :

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기