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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42579

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 장르 속 노래들의 총 재생 횟수를 담을 HashMap, 장르 이름 -> 번호로 변환할 HashMap, 장르 총 재생 횟수 내림차순 용 우선순위 큐, 장르 번호를 통해 해당 장르 속 노래들의 재생 횟수를 내림차순으로 정렬할 ArrayList<우선순위큐> 생성
2. 주어진 genres와 plays 배열들 돌며
   • 현재 노래가 새로운 장르라면 장르 번호 부여, 총 재생 횟수 추가, 해당 장르 속 노래들의 재생이 담길 우선 순위 큐 생성, 현재 노래 정보 추가
   • 현재 노래가 기존 장르라면 장르 총 재생 횟수 추가, 장르 속 노래들의 우선 순위 큐에 해당 노래 정보 추가
3. 앞선 장르 속 노래들의 총 재생 횟수가 담긴 HashMap을 돌며 우선순위큐에 삽입
4. while문을 통해 장르에 대한 우선순위 큐에서 장르(장르 번호)를 순서대로 뽑아 해당 장르 번호에 대한 노래들이 담긴 우선순위큐에서 최대 2번까지 노래의 고유 번호를 뽑아 해답 배열에 추가

 문제에서 요구하는 앨범 생성 방식이 알고리즘 상 매우 어려운 방식은 아니지만, 해당 방식을 따라가기 위해 주어진 genres, plays 배열 속 데이터들의 전처리가 매우 까다로웠던 문제이다.

 결국 앨범에 노래(각 장르 당 최대 노래 2개)를 수록하는 기준으로는 "1. 총 재생 횟수에 대한 장르를 먼저 2. 해당 장르 내에선 노래의 재생 횟수의 내림차순 3. 재생 횟수가 같으면 노래의 고유번호가 작은 순"이기 때문에 해당 요구를 따르게 위해선 장르의 총 재생 횟수가 담기고 이를 정렬할 자료구조, 특정 장르 속 노래들만 담긴 상태로 조건(노래 재생횟수 내림차순, 노래 고유 번호 오름차순)으로 정렬할 자료구조가 각각 필요하다.

 우선 장르의 총 재생 횟수가 담기고 이를 정렬할 자료구조의 경우, 장르의 총 재생 횟수가 저장될 자료구조(HashMap)/장르를 정렬할 자료구조(우선순위큐)를 각각 따로 생성하여 우선 장르의 총 재생 횟수를 모두 구한 다음 반복문을 통해 우선순위큐에 넣는 방식으로 나누어 진행했다.

 그 다음에는 각 노래에 대한 정렬인데, 노래의 경우 해당 장르들의 노래로만 이루어진 우선순위 큐를 생성한 다음 노래의 장르에 따라 맞는 우선 순위큐에 노래를 넣어주면 된다. 하지만 이 경우 제일 중요한 점이 장르는 문자열이지만, 우리가 자료구조를 생성(ArrayList<PriorityQueue<SongInfor>>)할 때는 접근을 위해 인덱스가 필요하여 장르 -> 인덱스(장르 번호)로 변환해줄 과정이 필요하다. 그렇기에 앞선 장르의 총 재생 횟수를 추가해주는 과정에서 기존에 없던 장르면 인덱스(장르 번호)를 부여해주는 과정을 추가하고, 이후 얻은 인덱스를 통해 해당 장르 속 노래들이 담긴 우선 순위큐에 노래 정보를 추가해주면 된다.

 이렇게 데이터의 전처리가 끝나면 답을 도출하는 과정은 매우 간단하다. 장르들의 총 재생횟수가 담긴 우선순위 큐에서 장르 번호를 순서대로 뽑아, 해당 장르 속 노래들로 이루어진 우선순위큐에 접근해 필요한 횟수만큼 노래를 뽑아 해당 고유 번호를 답에 추가해주면 된다.

 

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> answerArrayList = new ArrayList<>(); //해답 생성용 ArrayList
        HashMap<String, Integer> genreTotalPlay = new HashMap<>(); //장르 속 노래들의 총 재생 횟수
        PriorityQueue<GenreInfor> genreTotalPlaySort = new PriorityQueue<>(); //장르 재생 우선순위 큐
        HashMap<String, Integer> genreToIndex = new HashMap<>(); //장르 -> 장르 번호 전환용 해시
        ArrayList<PriorityQueue<SongInfor>> songPlayInGenre = new ArrayList<>(); //장르 번호를 이용한 노래 정렬 우선순위 큐
        int genreIndex = 0;//장르 번호 생성용 int

        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i]; //장르
            int play = plays[i]; //노래 재생 횟수
            SongInfor songInfor = new SongInfor(i, play); //노래 정보 생성

            if (genreTotalPlay.containsKey(genre)) {//기존 장르인 경우
                genreTotalPlay.replace(genre, genreTotalPlay.get(genre) + play); //장르 총 재생 횟수 추가
                songPlayInGenre.get(genreToIndex.get(genre)).add(songInfor); //장르 속 노래들의 우선 순위 큐에 추가
            } else {//새로운 장르인 경우
                genreTotalPlay.put(genre, play); //새롭게 총 재생 횟수 추가
                genreToIndex.put(genre, genreIndex++); //장르 번호 생성

                songPlayInGenre.add(new PriorityQueue<>()); // 장르 속 노래들의 우선 순위 큐 생성
                songPlayInGenre.get(songPlayInGenre.size() - 1).add(songInfor); //현 노래 정보 추가
            }
        }

        for (Map.Entry<String, Integer> element : genreTotalPlay.entrySet()) {//전체 장르 정보를 돌며 우선순위 큐에 추가
            GenreInfor genreInfor = new GenreInfor(element.getKey(), element.getValue());

            genreTotalPlaySort.add(genreInfor);
        }

        while (!genreTotalPlaySort.isEmpty()) { //장르 재생 횟수 최다 순서대로
            GenreInfor genreInfor = genreTotalPlaySort.poll();
            int genreNum = genreToIndex.get(genreInfor.genre); //장르 번호 get
            int index = 0; //해답 ArrayList에 옮길 노래 개수
            PriorityQueue<SongInfor> songPlay = songPlayInGenre.get(genreNum); //해당 장르 속 노래들의 우선순위 큐

            while (!songPlay.isEmpty() && index < 2) { //해답에 노래 추가
                SongInfor songInfor = songPlay.poll();
                answerArrayList.add(songInfor.songNum);
                ++index;
            }
        }

        int[] answer = new int[answerArrayList.size()]; //Integer ArrayList -> int answer 배열
        for (int i = 0; i < answerArrayList.size(); i++) {
            answer[i] = answerArrayList.get(i);
        }

        return answer;
    }

    class SongInfor implements Comparable<SongInfor>{ //노래 정보
        int songNum, play;

        public SongInfor(int songNum, int play) {
            this.songNum = songNum;
            this.play = play;
        }

        @Override
        public int compareTo(SongInfor o) {
            if (this.play > o.play) {
                return -1;
            } else if (this.play == o.play) {
                if (this.songNum < o.songNum) {
                    return -1;
                } else {
                    return 1;
                }
            } else {
                return 1;
            }
        }
    }

    class GenreInfor implements Comparable<GenreInfor> {//장르 정보
        String genre;
        int totalPlay;

        public GenreInfor(String genre, int totalPlay) {
            this.genre = genre;
            this.totalPlay = totalPlay;
        }

        @Override
        public int compareTo(GenreInfor o) {
            if (this.totalPlay > o.totalPlay) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}

결과