P42579. 베스트앨범

문제

제출 코드

• 사용 알고리즘 : 해시, 자료구조, 우선순위 큐

곡 정보를 담을 클래스를 구현해서 우선순위대로 뽑으면 되는 문제이다.

곡을 정렬하기 위해, 각 장르들의 누적 재생 수를 먼저 구해줘야한다.

문제가 전체적으로 어렵진 않았지만, 풀이에 적절한 자료구조 선정과정에서 조금 헤멨다.

그리고, 이번에는 List를 Array로 변환하는 방법을 바꿔봤다.

원래 int형과 같은 primitive 타입은 toArray()를 사용할 수 없기에, 이전에는 int 배열을 만들고 반복문을 돌려 하나씩 값을 옮겨줬는데 이젠 좀 귀찮아졌다.

list.stream().mapToInt(i -> i).toArray();

위 방식은 리스트를 스트림으로 변환한 후에, map을 이용해서 intStream으로 가져온 뒤 toArray를 사용하는 방법이다.

한줄로 간단하게 변환할 수 있으니 외워두면 문제 풀 때 편할듯 싶다.

주의해야할 점은, 자바의 스트림(Stream)은 Java 8부터 지원되기 시작했으므로 이전버전에서는 사용할 수 없다. 근데 요즘 8버전 미만을 사용하는 경우는 거의 없지않나싶기도?

import java.util.*;

class Solution {
    static class Song implements Comparable<Song>{
        int idx, genreCnt, songCnt;
        Song(int idx, int genreCnt, int songCnt){
            this.idx = idx;
            this.genreCnt = genreCnt;
            this.songCnt = songCnt;
        }
        @Override
        public int compareTo(Song o){ // 장르 재생 수 > 곡 재생 수 > 곡 인덱스 순서로 정렬
            if(this.genreCnt == o.genreCnt){
                if(this.songCnt == o.songCnt) return this.idx - o.idx;
                else return o.songCnt - this.songCnt;
            }else return o.genreCnt - this.genreCnt;
        }
    }

    public int[] solution(String[] genres, int[] plays) {
        int size = plays.length;

        // 1. 장르 재생 수 누적
        Map<String, Integer> genreList = new HashMap<String, Integer>();
        for(int i=0; i<size; i++){
            if(!genreList.containsKey(genres[i])) genreList.put(genres[i], plays[i]);
            else genreList.replace(genres[i], genreList.get(genres[i])+plays[i]);
        }

        // 2. 우선순위대로 곡 정렬
        PriorityQueue<Song> queue = new PriorityQueue<Song>();
        for(int i=0; i<size; i++){
            queue.add(new Song(i, genreList.get(genres[i]), plays[i]));
        }

        // 3. 곡 수록하기
        List<Integer> answer = new ArrayList<Integer>();
        int genreCnt=0, songCnt=0, genreSize = genreList.size();

        while(!queue.isEmpty() || genreCnt<genreSize){
            Song now = queue.poll();
            answer.add(now.idx);

            if(++songCnt==2 || queue.isEmpty() || queue.peek().genreCnt!=now.genreCnt){
                ++genreCnt;
                songCnt = 0;

                while(!queue.isEmpty()){ // 해당 장르에 남은 곡들 버리기
                    if(queue.peek().genreCnt==now.genreCnt) queue.poll();
                    else break;
                }
            }
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}