[프로그래머스 / Java] 베스트앨범(Lv.3)

문제 풀이 날짜: 2023.05.03
포스트 작성일: 2023.05.06

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

프로그래머스 코딩테스트 고득점Kit 해시 편 : 베스트앨범 (Lv.3) (문제 링크)

 

키워드

해시맵, 우선순위 큐

 

풀이 접근법

• 주어진 조건에 부합하는 노래를 ‘두 곡’만 선정하는데, 만약 조건에 부합하는 것이 오직 한 곡만 존재한다면 한 곡만 수록해야 한다. 조건은 다음과 같다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록
   • 각 노래별로 총 재생수를 집계하고, 해당 장르의 곡 목록을 탐색한다 ⇒ 정렬 필요
2. 장르 내에서 많이 재생된 노래를 먼저 수록
   • 그 장르 내에서 가장 재생수가 높은 노래 탐색 ⇒ 정렬 필요
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
   • 별도의 Comparator를 이용한 정렬 기준이 필요하다.

• 장르별 재생수를 집계한 다음에 수록은 어떻게 할까?
  • 우선순위 큐에 모든 장르를 넣고, 재생수가 높은 장르를 하나씩 뽑는다. (poll) ⇒ Entry 자료구조 필요
  • 해당 장르의 노래들로 Entry<장르, 재생수> 리스트를 만들어 사전순의 반대로 정렬한다.
  • 앨범 등록을 마친 장르는 자연히 우선순위 큐에서 삭제된 상태이다.
  • 큐에 더 이상 들어있는 것이 없다면 종료한다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};

        HashMap<String, Integer> map = new HashMap<>();

        //장르별 총 재생횟수 집계
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];

            map.put(genre, map.getOrDefault(genre, 0) + play);
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue())); //내림차순

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.add(entry);
        }

        ArrayList<Integer> result = new ArrayList<>();

        //pq에서 재생수가 높은 장르 순으로 뽑으며 앨범에 수록한다.
        while(!pq.isEmpty()) {
            Map.Entry<String, Integer> entry = pq.poll();
            String genre = entry.getKey();

		//poll()로 뽑은 장르의 노래들만 모은다.
            ArrayList<int[]> list = new ArrayList<>();
            for(int i = 0; i < genres.length; i++) {
                if(genre.equals(genres[i])) { 
                    int[] a = {i, plays[i]};
                    list.add(a);
                }
            }

            Collections.sort(list, (o1, o2) -> (Integer.compare(o2[1], o1[1])));

            int avaliableSize = 0;
            if(list.size() >= 2) {
                avaliableSize = 2;
            }
            else if (list.size() == 1) {
                avaliableSize = 1;
            }

            for(int i = 0; i < avaliableSize; i++) {
                int num = (list.get(i))[0];
                result.add(num);
            }
        }

        answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }
}

---

해시 문제집에 있었지만 해시 그 자체보다는 여러 자료구조를 알아야 풀기 쉬운 문제인 것 같다. 시간을 정해놓고 풀었기 때문에 급하게 마무리했으나, 개인적으로 코드를 더 깔끔하게 짰으면 좋았을 텐데 하는 아쉬움이 있다. Stream을 사용하면 몇몇 코드를 깔끔하게 다듬을 수 있을 듯하다. 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day1/BestAlbum.java