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

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

코딩테스트 연습 - 베스트앨범

아이디어

1. 장르 데이터 정리

Map<장르명, 총 재생수> 변수를 사용하여 각 장르별 총 재생수를 계산한다.

장르 명, 총 재생수를 멤버 변수로 가지는 Genre class를 정의하고, Comparable을 implements 하여 총 재생수를 바탕으로 Genre끼리 대소비교가 가능하도록 해 준다. 이 때, 내림차순으로 정렬될 수 있도록 한다.

위 Map에 만들어놓은 정보를 바탕으로 각 장르별로 Genre class의 instance를 만들고, PriorityQueue를 사용해 내림차순으로 정렬시킨다.

 

2. 각 장르별 노래 데이터 정리

Map<장르명, PriorityQueue<노래>> 변수를 사용하여 각 장르마다 그 장르에 속한 노래들에 대한 정보를 정리한다.

Song class는 멤버 변수로 고유 번호와 재생 횟수를 가지도록 하고, Comparable을 implements 하여 재생 수를 바탕으로 Song class의 instance끼리 대소비교가 가능하도록 해 준다. 마찬가지로 내림차순으로 정렬될 수 있도록 한다.

주어진 genres, plays array를 순회하며, Map.get(genres[i]) 를 통해 얻을 수 있는 해당 장르의 PriorityQueue에 재생 횟수 plays[i], 고유 번호 i를 가지는 Song class의 instance를 offer 한다.

 

3. 정답 확인

1의 PrioritQueue에서 poll을 하면 차례대로 총 재생횟수가 많은 베스트 장르를 얻을 수 있다.

2의 Map에서 위 결과를 get 하면, 해당 장르의 노래들을 담은 PriorityQueue를 얻을 수 있다. 이 PriorityQueue에서 최대 2개의 원소를 poll한다.

이 과정을 1의 PriorityQueue가 empty 될 때 까지 반복한다.

 

소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> plays4EachGenre = new HashMap<>(); // 장르명 : 총재생수
        for (int i = 0; i < genres.length; i++) {
            plays4EachGenre.put(genres[i], plays4EachGenre.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        // 1. 인기 "장르" 정렬
        PriorityQueue<Genre> bestGenres = new PriorityQueue<>();
        Set<String> genreNames = plays4EachGenre.keySet();
        for (String bestGenre : genreNames) {
            bestGenres.offer(new Genre(bestGenre,  plays4EachGenre.get(bestGenre)));
        }

        // 1-2. 각 장르별 Song 정렬
        Map<String, PriorityQueue<Song>> bestSongs4EachGenre = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            PriorityQueue<Song> pq4Songs = bestSongs4EachGenre.getOrDefault(genres[i], new PriorityQueue<>());
            pq4Songs.offer(new Song(plays[i], i));
            bestSongs4EachGenre.put(genres[i], pq4Songs);
        }

        // 2. 각 장르별 최대 2곡까지 뽑기
        List<Integer> answer = new ArrayList<>();
        while (!bestGenres.isEmpty()) {
            Genre currentGenre = bestGenres.poll();
            String currentGenreName = currentGenre.getGenreName();

            PriorityQueue<Song> pq4SongsOfEachGenre = bestSongs4EachGenre.get(currentGenreName);
            int size = Math.min(pq4SongsOfEachGenre.size(), 2);
            for (int i = 0; i < size; i++) {
                answer.add(Objects.requireNonNull(pq4SongsOfEachGenre.poll()).getRegNo());
            }
        }

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

class Song implements Comparable<Song> {
    private final int plays;
    private final int regNo;

    Song(int plays, int regNo) {
        this.plays = plays;
        this.regNo = regNo;
    }

    public String getGenre() {
        return this.genre;
    }

    public int getPlays() {
        return this.plays;
    }

    public int getRegNo() {
        return this.regNo;
    }

    @Override
    public int compareTo(Song o) {
        return o.getPlays() - this.plays;
    }
}

class Genre implements Comparable<Genre> {
    private final String genreName;
    private final int totalPlays;

    Genre(String genreName, int totalPlays) {
        this.genreName = genreName;
        this.totalPlays = totalPlays;
    }

    public String getGenreName() {
        return this.genreName;
    }

    public int getTotalPlays() {
        return this.totalPlays;
    }

    @Override
    public int compareTo(Genre o) {
        return o.getTotalPlays() - this.totalPlays;
    }
}

 

Review

아직 첫 번째 풀이여서 내용도, 아이디어도 깔끔하게 정리가 되지 못했다. 불필요한 중복도 보이고 수정/개선할 부분이 남아있다.

좀 더 유형정리를 잘 해 두어서 다음번 풀이때에는 보다 깔끔하고 빠르게 구현할 수 있도록 해 두어야겠다.