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

문제

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

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

 

풀이

Genre와 Song을 클래스로 구현하여 쉽게 풀 수 있다. 

해당 문제의 목적은 장르 별로 가장 많이 재생된 노래 두 개를 출력하는 것이다. 

 

아래의 같은 조건이 있다.

1. 장르 내 속한 노래의 총 재생 횟수가 가장 많은 장르 부터 출력 

- 모든 장르의 총 재생 횟수는 다르다. 

- 만약 장르내 속한 곡이 한 개라면 한 개만 출력한다.

2. 장르 내 재생이 많이 된 노래부터 출력

- 만약 재생 횟수가 같다면 고유 번호가 낮은 노래를 우선으로 출력한다. 

 

예제

["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 장르의 총 재생 횟수: 1450

pop 장르의 총 재생 횟수: 3100

=> pop장르의 노래 부터 출력

 

pop장르 내 노래 고유번호/재생횟수 

1번 / 600회

4번 / 2500회

=> 4번, 1번 순으로 출력

 

classic 장르 내 노래 고유번호/재생횟수

0번 / 500회

2번 / 150회

3번 / 800회

=> 3번, 0번 순으로 출력 

 

답: 4, 1, 3, 0

 

구현

1. Genre 클래스에 총 재생 횟수와 노래를 담을 자료구조 변수를 선언한다. 

• 출력 시 Genre내 총 재생횟수 순으로 정렬 해야 하므로 Comparable을 implements 하여 CompareTo를 총 재생횟수 내림차순으로 구현해 놓는다. 
• 노래를 담을 자료 구조는 우선순위 힙을 사용한다. 

2. Song 클래스에 고유 번호와 재생 횟수를 담을 멤버 변수를 선언한다.

• Compabale을 implements하여 compareTo를 재생 횟수 내림 차순으로 구현, 만약 재생 횟수가 같다면 고유번호 오름차순으로 구현한다.

3. Key: Genre명, Value: Genre 객체를 넣을 GenreMap을 생성한다. 

4. Input을 받아서 처리한다. 

• GenreMap에 해당 Genre가 없다면 새로 넣어준다. 
• Map에 이미 있다면, Genre객체를 가져와서 Song객체를 생성하여 넣어준다.

5. 맵에있는 장르 객체를 리스트에 담아서 Collections.sort를 수행한다. 

6. 출력 한다.

 

 

소스코드

import java.util.*;

class Genre implements Comparable<Genre>{
    int totalPlay;
    PriorityQueue<Song> songs;
    
    public Genre(){
        this.totalPlay = 0; 
        this.songs = new PriorityQueue<Song>();
    }
    
    public void add(Song song){
        totalPlay += song.play;
        songs.offer(song);
    }
    
    @Override
    public int compareTo(Genre g1){
        return g1.totalPlay - this.totalPlay;
    }
}

class Song implements Comparable<Song>{
    int no;
    int play;
    
    public Song(int no, int play){
        this.no = no; 
        this.play = play;
    }

    @Override
    public int compareTo(Song s1){
        int rs = s1.play - this.play;
        if(rs == 0) rs = this.no - s1.no;
        return rs;
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 장르 별로 가장 많이 재생된 노래 두 개 모아서 출시 
        // 1. 장르 먼저 선택 (모든 장르는 재생 횟수 다름, 곡 한 개면 한 개만수록)
        // 장르 내 속한 노래의 총 재생횟수가 가장 많은 장르부터 
        // 2. 노래 선택 
        // 장르 내 재생이 많이 된 노래부터 
        // 3. 노래 재생횟수가 같다면? 
        // 고유 번호가 낮은 노래 우선
        
        
        // 장르 맵에 장르 객체를 생성하여 넣는다. 
        // 장르 객체 내 노래큐에 노래를 넣는다. (노래가 들어 갈때 totalPlay가 증가)
        // 노래큐는 힙으로 생성되어 있어서, 들어갈 때 자동으로 재생수, 고유번호로 정렬
        HashMap<String, Genre> genreMap = new HashMap<String, Genre>();
        int len = genres.length;
        for(int i = 0; i < len; i++){
            String g = genres[i];
            if(!genreMap.containsKey(g)){
                genreMap.put(g, new Genre());
            } 
            genreMap.get(g).add(new Song(i, plays[i]));
        }
        
        
        // 장르 총 재생 수가 많은 순으로 정렬
        ArrayList<Genre> list = new ArrayList<Genre>();
        for(String key : genreMap.keySet()){
            list.add(genreMap.get(key));
        }
        Collections.sort(list);
        
        
        // 재생수가 많은 장르 순, 재생 수가 많은 노래 순으로 곡의 고유번호 출력
        ArrayList<Integer> answer = new ArrayList<Integer>();
        for(Genre genre : list){
            int cnt = 0;
            while(!genre.songs.isEmpty()){
                if(cnt >= 2) break;
                answer.add(genre.songs.poll().no);
                cnt++;
            }  
        }
        
        return answer.stream().mapToInt(x->x).toArray();
    }
}