베스트 앨범

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

문제설명

• 주어진 파라미터: String[] 노래의 장르 genres, int[] 재생 횟수 plays
• 반환값: int[]
• 장르별로 가장 많이 재생된 노래를 두개씩 모아 베스트 앨범 출시
• 노래는 고유번호로 구분
• 노래 수록 기준
  • 속한 노래가 많이 재생된 장르 먼저
  • 장르 내 많이 재생된 노래 먼저
  • 장르 내 재생횟수 같을 경우 고유 번호 낮은 노래 먼저

풀이방식

1. genres 의 인덱스가 그 곡의 고유번호

2. 장르, 횟수 길이는 10^4 이하 → 2중 반복 불가

3. 별도의 클래스 필요

   class Solution {
       public class Song{
           String genres;                   // 장르명                          
           PriorityQueue<int[]> songs;      // 장르 곡당 인덱스, 실행횟수                  
           int sum = 0;                     // 해당 장르 총 실행횟수                
   }

4. sum 역순 기준으로 PriorityQueue 생성 → 최종 결과에 사용

   • 4개가 채워질때까지 장르 당 곡을 2곡씩 꺼내기

코드

import java.util.*;

class Solution {
    public class Song{
        String genres; 
        PriorityQueue<int[]> songs;
        int sum = 0;
        
        public Song(String name){
            this.genres = name;
            this.songs = new PriorityQueue<>((a, b) -> {
                // 재생 수 높은 순 정렬 
                if(b[1] != a[1]) return b[1] - a[1];
                
                // 재생 수가 같다면 인덱스 낮은 순 정렬
                return a[0] - b[0];
            });
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        PriorityQueue<Song> songPq = new PriorityQueue<>((a, b) -> {
            return b.sum - a.sum;
        });
        List<Song> existList = new ArrayList<>(); // 존재하는지 확인 용도
        
        for(int i = 0; i < genres.length; i++){
            String songName = genres[i];
            int songPlays = plays[i];
            Song curSong = null;
            
            // existList에 들어가있는지 확인
            for(Song s : existList){
                // 존재하는 경우 
                if(s.genres.equals(songName)){
                    curSong = s;
                    break;
                }
            }
            
            // existList에 없으면 = Pq 에도 없음  
            if(curSong == null){
                // 새로운 객체 생성
                Song newSong = new Song(songName);
                newSong.songs.offer(new int[]{i, songPlays});
                newSong.sum += songPlays;
                
                // Pq, List에 추가 
                existList.add(newSong);
                songPq.offer(newSong);
            }else{
             // existList에 있으면 업데이트 
                curSong.songs.offer(new int[]{i, songPlays});
                curSong.sum += songPlays;
                
                songPq.remove(curSong);
                songPq.offer(curSong);
            }
        }
        
        // 결과 생성
        List<Integer> answer = new ArrayList<>();
        while (!songPq.isEmpty()) {
            Song currentSong = songPq.poll();

            // 각 장르에서 최대 2곡 선택
            int count = 0;
            while (!currentSong.songs.isEmpty() && count < 2) {
                answer.add(currentSong.songs.poll()[0]);
                count++;
            }
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();

        
    }
}

회고

이번 문제는 설계하는 부분에서 어려움을 겪었습니다. 회고에 적기엔 글이 너무 길어질 것 같아 추가적인 포스팅으로 회고를 진행하겠습니다.

1. CompareTo 와 람다
2. Array -> ArrayList / ArrayList -> Array

---

휴 ~