[Programmers] 고득점 Kit - Hash : 베스트앨범 #42579

문제 링크

베스트앨범

문제 조건

• 속한 노래가 많이 재생된 장르를 먼저 수록한다.
• 장르 내에서 많이 재생된 노래를 먼저 수록한다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
  ​

  변수 설명

  ​
• 매개변수
  • genres : 노래의 장르를 나타내는 문자열 배열
  • plays : 노래별 재생 횟수를 나타내는 정수 배열
• Song : 고유 번호(idx)와 재생 횟수(plays)를 가진 클래스
• rankHash : 장르의 순위 결정을 위한 HashMap
• pq : 장르 순위 판별을 위한 우선순위 큐
• songRank : 각 장르별 음악 1, 2위
  ​

  코드 설명

1. 30~42줄

• 재생 횟수(plays) 큰 것이 더 크도록, 재생 횟수가 같다면 순서(idx)를 비교하여 더 낮은 것이 더 크도록 설정

2. rankHash에 genres와 plays를 각각 key, value로 넣어준다.
3. 장르의 순위를 위해 rankhash의 values을 우선순위 큐 pq에 넣어준다.

• 이 때, 내림차순으로 저장해야하기 때문에 reverseOrder()를 사용한다.

4. 60~63줄

• 재생 횟수(plays)가 더 중요하므로 rankHash의 key와 value를 바꿔준다.

5. 4번을 이용하여 장르의 순위를 구한다.
6. 각 장르의 노래 1, 2위를 뽑아준다.
   ​

   배운 점

• Collections.reverseOrder
  • (+) Integer를 갖는 우선순위 큐 내림차순 정렬방법 : Collections.reverseOrder()
• implements Comparable
  • Comparable을 implements를 이용하여 인터페이스를 구현하여 compareTo를 class에 맞게 바꿔준다.

    문제 해답

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;

// 고유 번호(idx)와 재생 횟수(plays)를 가진 Song 클래스 생성
class Song implements Comparable<Song> {
    public int idx;
    public int plays;
    public Song(int idx, int plays) {
        this.idx = idx;
        this.plays = plays;
    }

    //재생 횟수(plays) 큰 것이 더 크도록, 재생 횟수가 같다면 idx를 비교하여 더 낮은 것이 크도록 설정
    @Override
    public int compareTo(Song o) {
        if (this.plays == o.plays) {
            if (this.idx > o.idx) {
                return 1;
            } else {
                return -1;
            }
        } else if (this.plays < o.plays) {
            return 1;
        } else {
            return -1;
        }
    }
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        //장르의 순위 결정을 위한 Hash 생성
        HashMap<String, Integer> rankHash = new HashMap<>();
        int len = plays.length;
        for (int i = 0; i < len; i++)
            rankHash.put(genres[i], rankHash.getOrDefault(genres[i], 0) + plays[i]);


        //장르 순위 판별을 위한 우선순위 큐 생성
        // 내림차순으로 저장해야하기 때문에 reverseOrder()를 사용했다.
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(rankHash.size(), Collections.reverseOrder());
        for (Integer value : rankHash.values())
            pq.add(value);

        //모든 장르는 재생된 횟수가 다르므로 rankHash의 Key, Value를 바꾼 HashMap 생성
        HashMap<Integer, String> rankHashReverse = new HashMap<>();
        for (String key : rankHash.keySet()) {
            rankHashReverse.put(rankHash.get(key), key);
        }

        //장르의 재생 횟수를 이용하여 가장 높은 장르부터 rankArr에 순서대로 저장(장르의 순위 선정 완료)
        int pqLen = pq.size();
        String[] rankArr = new String[pqLen];
        for (int i = 0; i < pqLen; i++) {
            rankArr[i] = rankHashReverse.get(pq.poll());
        }

        //장르의 순위는 정해졌으니 각 노래의 1,2위를 뽑기 위한 HashMap 생성
        HashMap<String, PriorityQueue<Song>> songsRank = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (songsRank.containsKey(genres[i])) {
                songsRank.get(genres[i]).add(new Song(i, plays[i]));
            } else {
                songsRank.put(genres[i], new PriorityQueue<Song>());
                songsRank.get(genres[i]).add(new Song(i, plays[i]));
            }
        }

        //정답리스트를 만들고 rankArr에 저장한 장르 순서대로 우선순위 큐에서 우선 순위가 높은 Song 하나씩 뽑아서 idx 저장
        ArrayList<Integer> answerArrList = new ArrayList<Integer>();
        for (int i = 0; i < rankArr.length; i++) {
            answerArrList.add(songsRank.get(rankArr[i]).poll().idx);
            //해당 장르에 한 곡이 전부라면 if 문 통과
            if (songsRank.get(rankArr[i]).peek() != null) {
                answerArrList.add(songsRank.get(rankArr[i]).poll().idx);
            }
        }

        //정답 리스트를 Array 형태로 변환 .toArray()는 Object[] 형태로 나오므로 int[] 형태로 바꾸어줌
        int[] answerArr = new int[answerArrList.size()];
        Object[] answerArrObj = answerArrList.toArray();
        for (int i = 0; i < answerArrObj.length; i++) {
            answerArr[i] = (int) answerArrObj[i];
        }

        return answerArr;
    }
}

​