[프로그래머스] 알고리즘 고득점 kit - 베스트앨범 (Hash)

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42579

 

 

 

<노래를 수록하는 기준>

기본 조건: 각 장르당 두 개의 노래를 수록한다

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

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

3rd. 장르 내에서 재생 횟수가 같을 경우, 고유 번호가 낮은 순으로 수록한다

 

 

<입출력 데이터 예시 및 설명>

 •    장르의 종류는 100개 미만

 •    모든 장르는 재생 횟수가 다름

 •    genres[i]는 고유번호가 i 인 노래의 장르

 •    plays[i]는 고유번호가 i 인 노래의 재생 횟수

 •    장르에 수록된 곡이 하나라면, 하나의 곡만 선택

 •    genres 와 plays 배열은 1:1 매칭 구조이며 범위는 1 ~ 10,000

 

 

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4,1,3,0]

 

0번 노래는 classic 이며, 500회 재생됨

1번 노래는 pop 이며, 600회 재생됨

2번 노래는 classic 이며, 150회 재생됨

3번 노래는 classic 이며, 800회 재생됨

4번 노래는 pop 이며, 2500회 재생됨

 

classic 장르는 총 1,450회 재생되었으며, 재생 횟수가 상대적으로 높은 3번과 0번이 순차적으로 베스트 앨범에 수록될 예정

pop 장르는 총 3,100회 재생되었으며, 재생 횟수가 상대적으로 높은 4번과 1번이 순차적으로 베스트 앨범에 수록될 예정

(총 재생 횟수 비교시 pop(3,100) > classic(1,450) 이므로 pop 장르가 먼저 수록될 예정)

 

따라서 베스트앨범은 4번, 1번, 3번, 0번 순으로 구성된다

 

 

<접근 방법>

노래의 정보를 저장하는 HashMap 생성

장르의 총 재생 횟수를 저장하는 HashMap 생성

각 장르에서 재생 횟수가 가장 높은 두 곡을 우선순위 큐(Priority Queue)로 추출

 

 

<코드 작성>

initializeMaps

for 루프를 사용하여 totalPlayCntByGenre 맵에 getOrDefault 를 사용하여

key: 장르, value: 장르별 총 누적 재생 횟수 삽입

 

songIdxAndPlayCntByGenre 맵에 computeIfAbsent 를 사용하여

key: 장르, value: 해당 장르에 수록된 곡의 번호와 재생 횟수 list 형태로 삽입

 

void initializeMaps(String[] genres, int[] plays) {
    for (int i = 0; i < genres.length; i++) {
        totalPlayCntByGenre.put(genres[i], totalPlayCntByGenre.getOrDefault(genres[i], 0) + plays[i]);
        songIdxAndPlayCntByGenre.computeIfAbsent(genres[i], k -> new ArrayList<>())
        .add(new int[] { i, plays[i] });
    }
}

 

(i = 0, genres[0] = "classic", plays[0] = 500)

totalPlayCntByGenre 에 <"classic" , 500> 삽입

songByGenreAndPlayCnt 에 <"classic" , <[0,500]>> 삽입

 

(i = 1, genres[1] = "pop", plays[1] = 600)

totalPlayCntByGenre 에 <"pop" , 600> 삽입하여 

<"classic" , 500> , <"pop" , 600>

songByGenreAndPlayCnt 에 <"pop" , <[1,600]>> 삽입하여

<"classic" , <[0,500]>> , <"pop" , <[1,600]>>

 

(i = 2, genres[2] = "classic", plays[2] = 150)

totalPlayCntByGenre 에 <"classic" , +150> 삽입하여

<"classic" , 650> , <"pop" , 600>

songByGenreAndPlayCnt 에 <"classic" , <[2,150]>> 삽입하여

<"classic" , <[0,500] , [2,150] >> , <"pop" , <[1,600]>>

 

(i = 3, genres[3] = "classic", plays[3] = 800)

totalPlayCntByGenre 에 <"classic" , +800> 삽입하여

<"classic" , 1450> , <"pop" , 600>

songByGenreAndPlayCnt 에 <"classic" , <[3,800]>> 삽입하여

<"classic" , <[0,500] , [2,150] , [3,800] >> , <"pop" , <[1,600]>>

 

(i = 4, genres[4] = "pop", plays[4] = 2500)

totalPlayCntByGenre 에 <"pop" , +2500> 삽입하여

<"classic" , 1450> , <"pop" , 3100>

songByGenreAndPlayCnt 에 <"pop" , <[4,2500]>> 삽입하여

<"classic" , <[0,500] , [2,150] , [3,800] >> , <"pop" , <[1,600] , [4,2500]>>

 

sortGenresByPlayCntDesc

totalPlayCntByGenre.entrySet() 을 사용하여 <"장르" , "총 재생 횟수">

엔트리를 생성하여 키와 값에 동시에 접근 가능하도록 구현

 

getValue() 를 사용하여 각각의 value 값들을 비교하여

내림차순으로 정렬한 뒤 sortedGenres 배열에 담기

 

String[] sortGenresByPlayCntDesc() {
    List<Map.Entry<String, Integer>> genreList = new ArrayList<>(totalPlayCntByGenre.entrySet());
    genreList.sort((a, b) -> b.getValue().compareTo(a.getValue()));
        
    String[] sortedGenres = new String[genreList.size()];
    
    for (int i = 0; i < genreList.size(); i++) {
        sortedGenres[i] = genreList.get(i).getKey();
    }
    return sortedGenres;
}

 

genreList는 <"classic" : 1450 , "pop" : 3100> 로 처음 생성되며

sort 를 내림차순으로 진행하여 결과적으로 sortedGenres 는 ["pop" , "classic"]

 

createSongWithPriorityQueue

재생 횟수가 같을 경우 고유 번호를 기준으로 오름차순 정렬

재생 횟수가 다를 경우 재생 횟수를 기준으로 내림차순 정렬

 

PriorityQueue<int[]> createPriorityQueueForSong(List<int[]> songs) {
    PriorityQueue<int[]> queue = new PriorityQueue<>(
        (a, b) -> a[PLAY_COUNT] == b[PLAY_COUNT] ? a[SONG_INDEX] - b[SONG_INDEX] : b[PLAY_COUNT] 
        - a[PLAY_COUNT]
    );
    queue.addAll(songs);
    return queue;
}

 

 

topSongsForGenre

각 장르별로 createSongWithPriorityQueue 메소드를 호출하여

우선순위 큐로 정렬하 상위 두 곡을 topSongs 리스트에 추가

 

int[] topSongsForGenre(String[] sortedGenres) {
    List<Integer> topSongs = new ArrayList<>();
    for (String genre : sortedGenres) {
        PriorityQueue<int[]> queue = createPriorityQueueForSong(songIdxAndPlayCntByGenre.get(genre));
        for (int i = 0; i < TOP_SONGS_LIMIT && !queue.isEmpty(); i++) {
            topSongs.add(queue.poll()[SONG_INDEX]);
        }
    }

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

 

전체코드

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    final int SONG_INDEX = 0;
    final int PLAY_COUNT = 1;
    final int TOP_SONGS_LIMIT = 2;

    HashMap<String, Integer> totalPlayCntByGenre = new HashMap<>();
    HashMap<String, List<int[]>> songIdxAndPlayCntByGenre = new HashMap<>();

    public int[] solution(String[] genres, int[] playCnt) {
        initializeMaps(genres, playCnt);
        String[] sortedGenres = sortGenresByPlayCntDesc();
        return topSongsForGenre(sortedGenres);
    }

    void initializeMaps(String[] genres, int[] plays) {
        for (int i = 0; i < genres.length; i++) {
            totalPlayCntByGenre.put(genres[i], totalPlayCntByGenre.getOrDefault(genres[i], 0) 
            + plays[i]);
            songIdxAndPlayCntByGenre.computeIfAbsent(genres[i], k -> new ArrayList<>())
                                 .add(new int[] { i, plays[i] });
        }
    }

    String[] sortGenresByPlayCntDesc() {
        List<Map.Entry<String, Integer>> genreList = new ArrayList<>(totalPlayCntByGenre.entrySet());
        genreList.sort((a, b) -> b.getValue().compareTo(a.getValue()));
        
        String[] sortedGenres = new String[genreList.size()];
        for (int i = 0; i < genreList.size(); i++) {
            sortedGenres[i] = genreList.get(i).getKey();
        }
        return sortedGenres;
    }

    int[] topSongsForGenre(String[] sortedGenres) {
        List<Integer> topSongs = new ArrayList<>();
        for (String genre : sortedGenres) {
            PriorityQueue<int[]> queue = 
            createPriorityQueueForSong(songIdxAndPlayCntByGenre.get(genre));
            for (int i = 0; i < TOP_SONGS_LIMIT && !queue.isEmpty(); i++) {
                topSongs.add(queue.poll()[SONG_INDEX]);
            }
        }

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

    PriorityQueue<int[]> createPriorityQueueForSong(List<int[]> songs) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(
            (a, b) -> a[PLAY_COUNT] == b[PLAY_COUNT] ? a[SONG_INDEX] - b[SONG_INDEX] : 
            b[PLAY_COUNT] - a[PLAY_COUNT]
        );
        queue.addAll(songs);
        return queue;
    }
}