[프로그래머스 문제 풀이] [Level 3] 베스트앨범

문제 링크:

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

프로그래머스

풀이

노래를 수록하는 기준을 맞추기 위해서는 다음을 해야 합니다. 

1. 장르별 총 재생 수를 계산

2. 장르에 속하는 노래를 재생 수로 정렬

3. 재생 횟수가 같은 노래는 고유 번호가 낮은 노래가 먼저 오게 정렬

 

이를 위해서 Genre라는 class를 만들어 총 재생 수, 장르별 노래를 저장했습니다.

class Genre implements Comparable<Genre>{
    String name;
    int total;
    TreeMap<Integer, Integer> musics;
    
    public Genre(int index, int plays){
        total=plays;
        musics = new TreeMap<Integer, Integer>();
        musics.put(index, plays);
    }
    
    public void getMusics(int index, int plays){
        total+=plays;
        musics.put(index, plays);
    }
    
    public ArrayList<Integer> playList(){
        ArrayList<Integer> list = new ArrayList<Integer>();
        Iterator it = sortByValue(musics).iterator();
        while(it.hasNext()){
            Integer tmp = (Integer) it.next();
            list.add(tmp);
            if(list.size() == 2){
                break;
            }
        }
        return list;
    }
    
    public int compareTo(Genre g){
        Integer tt = this.total;
        Integer gt = g.total;
        return gt.compareTo(tt);
    }
    
    public List sortByValue(final Map map){
        List<Integer> list = new ArrayList();
        list.addAll(map.keySet());
         
        Collections.sort(list,new Comparator(){
             
            public int compare(Object o1,Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);
                 
                return ((Comparable) v2).compareTo(v1);
            }
             
        });
        return list;
    }
}

Genre에서 compareTo()를 override하는 것으로 정렬할 때 총 재생 수의 내림차순으로 정렬되게 합니다.

또한 playList()는 sortByValue()를 통해 TreeMap에 저장된 노래를 재생 수로 정렬해서 많이 재생된 노래를 두 개까지 list에 담아 반환합니다. 

 

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Genre> map = new HashMap<String, Genre>();
        
        for(int i = 0; i < genres.length; i++){
            String genre = genres[i];
            if(!map.containsKey(genre)){
                Genre tmp = new Genre(i, plays[i]);
                map.put(genre, tmp);
            }else{
                map.get(genre).getMusics(i, plays[i]);
            }
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Genre> gList = new ArrayList<Genre>();
        gList.addAll(map.values());
        Collections.sort(gList);
        
        for(int i = 0; i < gList.size(); i++) {
        	list.addAll(gList.get(i).playList());
        }
        
        int[] answer = new int[list.size()];
        
        for(int i = 0; i < list.size(); i++) {
        	answer[i] = list.get(i);
        	System.out.println(answer[i]);
        }
        
        return answer;
    }
}

class Genre implements Comparable<Genre>{
    String name;
    int total;
    TreeMap<Integer, Integer> musics;
    
    public Genre(int index, int plays){
        total=plays;
        musics = new TreeMap<Integer, Integer>();
        musics.put(index, plays);
    }
    
    public void getMusics(int index, int plays){
        total+=plays;
        musics.put(index, plays);
    }
    
    public ArrayList<Integer> playList(){
        ArrayList<Integer> list = new ArrayList<Integer>();
        Iterator it = sortByValue(musics).iterator();
        while(it.hasNext()){
            Integer tmp = (Integer) it.next();
            list.add(tmp);
            if(list.size() == 2){
                break;
            }
        }
        return list;
    }
    
    public int compareTo(Genre g){
        Integer tt = this.total;
        Integer gt = g.total;
        return gt.compareTo(tt);
    }
    
    public List sortByValue(final Map map){
        List<Integer> list = new ArrayList();
        list.addAll(map.keySet());
         
        Collections.sort(list,new Comparator(){
             
            public int compare(Object o1,Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);
                 
                return ((Comparable) v2).compareTo(v1);
            }
             
        });
        return list;
    }
}

전체 코드에서는 Genre 클래스를 통해 입력되는 정보를 저장하고 총 재생 수로 정렬합니다.

이때 HashMap을 사용해서 장르별로 노래를 저장하는 과정을 쉽게 했습니다.

이후 장르마다 playList()에서 반환되는 값을 저장해서 반환합니다.

 

후기

오랜만에 길게 코딩해서 재밌었습니다.

해쉬 문제는 알고리즘 자체는 어렵지 않아서 쉽게 풀 수 있는 것 같습니다.