[프로그래머스] 베스트앨범 (Java, 자바)

 

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

프로그래머스

 

🚀풀이

HashMap과 List 정렬을 알아야 하는 문제!

문제의 조건에서 

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

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

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록

위 세 조건을 만족시키기 위해서 장르 클래스, 노래 클래스를 만들었고 이들이 정렬될 수 있도록 Comparable을 상속받아 구현했다.

정렬을 할 때 고유 번호도 고려를 해야 하는데, 처음 리스트에 삽입할 때 고유 번호가 낮은 순서대로 정렬했기 때문에

Collection.sort()를 해도 고유번호가 낮은 순서대로 정렬되어 나오므로 고유 번호 정렬은 따로 구현하지 않았다.

이유는 Collection.sort()에서 사용되는 정렬 알고리즘은 Tim Sort인데 해당 정렬은 Stable Sort이기 때문이다.

 

장르를 정렬할때 장르 별 전체 노래 플레이수로 정렬을 해야 해서 List에 장르들을 닮아서 정렬을 한 뒤,

앞에서부터 장르들을 뽑아 각 장르 안에 노래들을 2개씩 뽑았다.

이때 노래들도 재생 횟수 별로 내림차순 정렬해야 하므로 정렬 후 2개를 뽑았다.

 

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {   
        // 장르 별 노래를 저장할 Map
        Map<String, List<Song>> map = new HashMap<>();
        // 주어진 입력에서 장르별로 노래들을 Map에 저장
        for(int i = 0; i < genres.length; i++) {
            if(map.get(genres[i]) == null) {
                map.put(genres[i], new ArrayList<>());
            }            
            map.get(genres[i]).add(new Song(i, plays[i]));
        }
        
        // 장르 별 전체 플레이 횟수를 저장할 List
        List<Genre> list = new ArrayList<>();
        // 장르 별 전체 플레이 횟수 저장
        for(String s : map.keySet()) {
            int sum = 0;
            for(int i = 0; i < map.get(s).size(); i++) {
                sum += map.get(s).get(i).play;
            }
            list.add(new Genre(s, sum));
        }
        
        // 장르 별 전체 플레이 횟수 내림차 순으로 정렬
        Collections.sort(list, Collections.reverseOrder());
        
        // 내림차순으로 정렬된 장르 리스트에서 장르 이름을 key값으로 사용하여
        // 장르멸 노래 저장한 Map의 장르별 노래 리스트에서 2곡씩 뽑기
        List<Integer> result = new ArrayList<>();
        for(int i = 0; i < list.size(); i++) {
            String key = list.get(i).name;  // 장르 이름
            int size = map.get(key).size(); // 장르에 속한 노래들의 개수
            Collections.sort(map.get(key), Collections.reverseOrder()); // 노래들 플레이 횟수로 내림차순 정렬
            for(int j = 0; j < size; j++) {
                if(j == 2) {    // 2개 넘어가면 안뽑기
                    break;
                }
                result.add(map.get(key).get(j).id); // 결과에 노래 고유 번호 저장
            }
        }        
        
        // 결과 List를 배열에 복사
        int[] answer = new int[result.size()];
        for(int i = 0; i < answer.length; i++) {
            answer[i] = result.get(i);
        }
        
        return answer;
    }
}

// 장르 정보 저장 클래스
class Genre implements Comparable<Genre> {
    String name;
    int totalPlay;
    public Genre(String name, int totalPlay) {
        this.name = name;
        this.totalPlay = totalPlay;
    }
    
    // 장르 총 플레이 수로 정렬
    @Override
    public int compareTo(Genre other) {
        return totalPlay - other.totalPlay;
    }
}

// 노래 정보 저장 클래스
class Song implements Comparable<Song> {
    int id, play;
    public Song(int id, int play) {
        this.id = id;
        this.play = play;
    }
    
    // 노래 플레이 수로 정렬
    @Override
    public int compareTo(Song other) {
        return play - other.play;
    }
}

 

 

결과