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

개요

• 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개 모아 베스트 앨범을 출시하려 한다.
• 노래는 고유 번호로 구분된다.
• 노래를 수록하는 기준
  • 속한 노래가 많이 재생된 장르를 먼저 수록
  • 장르 내에서 많이 재생된 노래를 먼저 수록
  • 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록

 

<조건>

• 알 수 없음

 

<입력>

• String[] genres: 노래의 장르
  • genres[i]: 고유번호가 i인 노래의 장르
  • 길이: 1 ~ 10,000(10^4)
  • 종류: 1 ~ 99
• int[] plays: 노래별 재생 횟수
  • plays[i]: 고유번호가 i인 노래가 재생된 횟수
  • 길이: 1 ~ 10,000(10^4)

※ genres와 plays의 길이는 같다. -> 둘 다 곡에 대한 정보이기 때문

※ 모든 장르는 재생된 횟수가 다르다.

 

 

<반환>

• 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return하라.

※ 장르에 속한 곡이 하나라면, 하나의 곡만 선택하라.

 

 

문제 풀이

먼저 지문을 통해 알고리즘을 생각해보았다.

 

1. 노래에 대한 정보{장르, (재생 횟수, 고유 번호)}를 자료구조에 넣기 + 장르 별 재생횟수 합 구하기.
2. 장르 별 재생횟수를 내림차순으로 정렬한다.
3. 각 장르마다 노래별 재생횟수, 고유번호로 정렬하고, 상위 2곡을 결과에 추가한다.
4. 결과를 리턴한다.

 

위와 같이 알고리즘은 깔끔하게 나왔는데

도저히 구현을 할 엄두가 안 나서 chatGPT의 도움을 받아 구현하였다.

(정말 잘 짠다..)

 

 

0. 자료구조

// 장르 별 재생횟수 합을 저장할 Map
Map<String, Integer> genrePlayCount = new HashMap<>();
// 장르 별 곡 리스트를 저장할 Map
Map<String, List<int[]>> genreSongs = new HashMap<>();

장르 별 곡 리스트를 구현할 때 Map 안에 List<int[]> 형태를 value로 넣는 방법은 진짜 생각도 못했다.

 

 

1. 각 자료를 자료구조에 넣기

// 1. 장르, (재생횟수, 고유번호)를 자료구조에 넣기
for (int i = 0; i < genres.length; i++) {
    genrePlayCount.put(genres[i], genrePlayCount.getOrDefault(genres[i], 0) + plays[i]);

    genreSongs.putIfAbsent(genres[i], new ArrayList<>());
    genreSongs.get(genres[i]).add(new int[]{plays[i], i});
}

장르 별 곡 리스트에 값을 넣을 때

putIfAbsent()를 통해 ArrayList<>()를 생성하고,

.get(genres[i]).add(new int[] {plays[i], i}); 를 통해 value 값을 넣는 것도 너무 신기했다.

 

 

2. 장르 별 재생횟수를 내림차순으로 정렬

// 2. 장르 별 재생횟수 내림차순으로 정렬
List<String> sortedGenres = new ArrayList<>(genrePlayCount.keySet());
sortedGenres.sort((a, b) -> genrePlayCount.get(b) - genrePlayCount.get(a));

람다식을 통해 정렬을 진행한다.

 

 

3. 각 장르마다 노래별 재생횟수, 고유번호로 정렬하고, 상위 2곡을 결과에 추가한다.

// 3. 각 장르마다 정렬 후 결과에 추가
for (String genre : sortedGenres) {
    // 장르 내 곡 정렬: 재생횟수 내림차순, 재생횟수 같으면 고유번호 오름차순
    List<int[]> songs = genreSongs.get(genre);
    songs.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

    // 상위 2곡까지 결과에 추가
    for (int i = 0; i < Math.min(2, songs.size()); i++) {
        answer.add(songs.get(i)[1]);
    }
}

 

 

 

4. 결과를 리턴한다.

return answer.stream().mapToInt(Integer::intValue).toArray();

 

 

전체 코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        // 장르 별 재생횟수 합을 저장할 Map
        Map<String, Integer> genrePlayCount = new HashMap<>();
        // 장르 별 곡 리스트를 저장할 Map
        Map<String, List<int[]>> genreSongs = new HashMap<>();

        // 1. 장르, (재생횟수, 고유번호)를 자료구조에 넣기
        for (int i = 0; i < genres.length; i++) {
            genrePlayCount.put(genres[i], genrePlayCount.getOrDefault(genres[i], 0) + plays[i]);

            genreSongs.putIfAbsent(genres[i], new ArrayList<>());
            genreSongs.get(genres[i]).add(new int[]{plays[i], i});
        }

        // 2. 장르 별 재생횟수 내림차순으로 정렬
        List<String> sortedGenres = new ArrayList<>(genrePlayCount.keySet());
        sortedGenres.sort((a, b) -> genrePlayCount.get(b) - genrePlayCount.get(a));

        // 결과를 저장할 리스트
        List<Integer> answer = new ArrayList<>();

        // 3. 각 장르마다 정렬 후 결과에 추가
        for (String genre : sortedGenres) {
            // 장르 내 곡 정렬: 재생횟수 내림차순, 재생횟수 같으면 고유번호 오름차순
            List<int[]> songs = genreSongs.get(genre);
            songs.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

            // 상위 2곡까지 결과에 추가
            for (int i = 0; i < Math.min(2, songs.size()); i++) {
                answer.add(songs.get(i)[1]);
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

 

 

배운 점

Map의 value 값으로 int 배열을 원소로 가지는 List를 집어 넣을 수 있다는 걸 배웠다.

 

이 과정에서 putIfAbsent()를 활용해 ArrayList를 생성하며,

값을 넣을 때는 get().add(new int[] {value, value}) 를 활용하는 것도 배웠다.

 

람다식으로 정렬하는 것도 꼭 익혀야 한다!