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

소스 보러가기
문제 보러가기

---

사용한 알고리즘 및 자료구조

HashMap,ArrayList

풀이
문제를 보고 HashMap 사용을 떠올랐다. 가장 먼저 생각한 것은 자바의 콜렉션을 최소화 하여 문제를 풀어내는 것 이었다. 그리고 총 4개의 콜렉션을 사용하여 문제를 풀었다.

먼저 파악해야 될 것은 정렬의 우선순위 요소 파악이다.

“장르 우선순위 , 노래 재생 횟수, 고유번호가 낮은 순서” 이렇게 우선순위가 선정되어 정렬이 된다. 파악한 우선순위로 차례차례 문제를 풀면 간단히 해결이 된다.

1. 각 장르별로 재생된 횟수 구하여 HashMap에 담기

2. 노래에 대한 구조체를 만들어 ArrayList에 담기

3. 정렬하기 : Collections.sort() 함수 이용

4. 정렬된 ArrayList에서 장르별 순서대로 2개씩 노래 새로운 ArrayList에 담기

간단하게 표현하면 이렇게 4단계로 문제가 풀린다. 자세한건 코드를 보면서 파악하기 바란다.

    // before test, have to delete 'static' keywords
    public static int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genresCheck = new HashMap<String, Integer>();
        HashMap<String, Integer> inputCheck = new HashMap<String, Integer>();
        ArrayList<Song> songList = new ArrayList<Song>();
        ArrayList<Integer> outputList = new ArrayList<Integer>();
        //1. genres count
        
        
        
        for(int g_idx = 0; g_idx < genres.length; g_idx++) {
 
            String g_str = genres[g_idx];
            songList.add(new Song(g_str,plays[g_idx],g_idx));
            
            if(genresCheck.containsKey(g_str)) {
                genresCheck.put(g_str, genresCheck.get(g_str)+plays[g_idx]);
            } else {
                
                genresCheck.put(g_str, plays[g_idx]);
            }
            
        }
        //2. sort
        
        Collections.sort(songList, new Comparator<Song>() {
            
            //s1 new
            @Override
            public int compare(Song s1, Song s2) {
                
                if(s1.genresName.equals(s2.genresName)) {
                    
                    if(s1.playCount != s2.playCount) {
                        return - (s1.playCount - s2.playCount);
                    } else {
                        
                        return (s1.songNum - s2.songNum);
                    }
                    
                } else {
                    
                    return -(genresCheck.get(s1.genresName) - genresCheck.get(s2.genresName));
                    
                }
                
            }
            
            
        }); 
        //3.checking
        for(int idx = 0; idx < songList.size(); idx++) {
            
            Song song = songList.get(idx);
            
            if(!inputCheck.containsKey(song.genresName)) {
                inputCheck.put(song.genresName, 1);
                outputList.add(song.songNum);
            } else {
                
                int cnt = inputCheck.get(song.genresName);
                
                if(cnt > 1) {
                    continue;
                } else {
                    inputCheck.put(song.genresName, cnt+1);
                    outputList.add(song.songNum);
 
                }
                
            }
            
        }
        
        int[] answer = new int[outputList.size()];
        
        for(int s_idx = 0; s_idx < answer.length; s_idx++) {
            answer[s_idx] = outputList.get(s_idx);
        }
 
 
        return answer;
    }
 
    static class Song {
        
        String genresName;
        int playCount;
        int songNum;
 
        public Song(String genresName, int playCount, int songNum) {
            
            this.genresName = genresName;
            this.playCount = playCount;
            this.songNum = songNum;
 
        }
 
    }