[프로그래머스 JAVA] 베스트앨범

[프로그래머스] 베스트앨범 : https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

---

문제 조건 정리

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

---

입력/출력

 

입력
genres -> ["classic", "pop", "classic", "classic", "pop"]

plays -> [500, 600, 150, 800, 2500]

 

출력

return -> [4, 1, 3, 0]

설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

- 고유 번호 3: 800회 재생
- 고유 번호 0: 500회 재생
- 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

- 고유 번호 4: 2,500회 재생
- 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

- 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

---

문제를 풀기 전

1. 맵 구조가 복잡하겠다고 생각함.

2. 각 입력의 순서를 표현하기 위해, 클래스 내에 idx 변수를 저장해야겠다고 생각함.

---

코드

 

import java.util.*;

class Solution {

        // 각 노래의 입력 순서와 재생 횟수를 표현할 수 있는 클래스 정의
        private static class Song implements Comparable<Song>{
            int idx, play;

            public Song(int idx, int play) {
                this.idx = idx;
                this.play = play;
            }

            // 우선 순위 큐 사용을 위한 비교 메서드 정의 (내림차순)
            @Override
            public int compareTo(Song o) {
                return o.play - this.play;
            }
        }

        public int[] solution(String[] genres, int[] plays) {

            // 각 장르의 총 재생 횟수를 저장
            HashMap<String, Integer> accMap = new HashMap<>();

            // 각 장르에 포함되는 노래들을 우선 순위 큐를 사용해서 저장
            HashMap<String, PriorityQueue<Song>> pqMap = new HashMap<>();

            // plays 배열 요소를 순회하기 위한 인덱스
            int idx = 0;

            for (String genre : genres) {
                // 해당 장르에 재생 횟수를 더함
                accMap.put(genre, accMap.getOrDefault(genre, 0) + plays[idx]);

                // 해당 장르에 Song 객체를 추가함
                // getOrDefault를 사용했기 때문에 아래와 같이 적으면 안됨 (Default 로 생성되는 pq에서 문제 발생)
                // (오류 발생) pqMap.getOrDefault(genre, new PriorityQueue<>()).offer(new Song(idx, plays[idx++]);
                PriorityQueue<Song> pq = pqMap.getOrDefault(genre, new PriorityQueue<>());
                pq.offer(new Song(idx, plays[idx++]));
                pqMap.put(genre, pq);
            }

            // 각 장르의 총 재생 횟수를 저장하는 accMap을 Map.Entry<String, Integer> 형태로 리스트로 변환
            List<Map.Entry<String, Integer>> entryList = new ArrayList<>(accMap.entrySet());

            // 리스트의 요소(Entry)들을 총 재생 횟수를 기준으로 내림차순 정렬
            Collections.sort(entryList, (entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));

            // 정답 저장 리스트
            // 배열로 구현시 각 장르에 1개의 곡이 있으면 예외 처리가 필요하므로 리스트로 정답을 저장
            List<Integer> answer = new ArrayList<>();

            // 정렬된 entryList의 요소를 순회
            for (Map.Entry<String, Integer> entry : entryList) {
                // 해당 장르에 속하는 우선 순위 큐를 가져옴
                PriorityQueue<Song> pq = pqMap.get(entry.getKey());

                int count = 0;
                // pq가 비어있지 않아야 함 && 각 장르당 노래가 2개를 초과하면 안됨
                while (!pq.isEmpty() && count++ != 2) {
                    // 우선 순위 큐이므로 해당 장르의 가장 많은 재생 횟수를 가진 노래부터 dequeue
                    Song song = pq.poll();
                    // dequeue 된 노래의 입력 순서를 저장
                    answer.add(song.idx);
                }
            }

            // 리스트로 저장된 answer 를 배열로 변경해서 출력 양식을 맞춤.
            return answer.stream().mapToInt(i -> i).toArray();
        }


    }

 

---

문제를 풀고 난 후

 

처음에는 우선 순위 큐를 사용하지 않고, 각 장르의 모든 노래를 정렬했었지만 비효율적이라고 생각하고 우선 순위 큐를 사용함!

해시맵을 복잡하게 사용하니 입력과 출력을 처리하면서 배우는 점이 많았음! 백준과 다른 맛.