[알고리즘 문제풀이] 프로그래머스 - 베스트앨범

yourjin·2022년 2월 27일

level3 알고리즘 해시(Hash)

알고리즘 문제풀이

목록 보기

15/28

TIL (2022.02.17)

➕ 오늘 푼 문제

프로그래머스 - 베스트앨범

➕ 아이디어

다음과 같은 해시를 생성한다.
- key = 장르, value = 수록된 곡들의 목록(고유번호) → playlist
- key = 장르, value = 수록된 곡들의 재생 횟수 합 -> playcount
재생 횟수의 내림차순으로 장르를 정렬한다.
전체 장르를 반복하며, 곡의 재생횟수, 곡 고유번호 순으로 정렬하여 2곡을 뽑는다.
(한 곡 밖에 없다면, 한 곡만 뽑는다.)

➕ Java 코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> answer = new ArrayList<>();
      	HashMap<String, ArrayList<Integer>> playlist = new HashMap<>();
        HashMap<String, Integer> playcount = new HashMap<>();
        
        for(int i=0; i<genres.length; i++){
            String g = genres[i];
            int p = plays[i];
            ArrayList<Integer> v = playlist.getOrDefault(g, new ArrayList<Integer>());
            v.add(i);
            
            playlist.put(g, v);
            playcount.put(g, playcount.getOrDefault(g, 0) + p);
        }
        
        Object[] sortedGenres = playcount.keySet().toArray();
       
        Arrays.sort(sortedGenres, new Comparator<Object>(){
            @Override
            public int compare(Object s1, Object s2){
                return playcount.get(s2) - playcount.get(s1);
            }
        });
        
        for(Object genre: sortedGenres){
            
            Collections.sort(playlist.get(genre), new Comparator<Integer>(){
                @Override
                public int compare(Integer i, Integer j){
                    if (plays[i] < plays[j]){
                        return 1;
                    }else if(plays[i] > plays[j]){
                        return -1;
                    }else{
                        if(i > j){
                        	return 1;
                        }else if(i < j){
                            return -1;
                        }else{
                            return 0;
                        }
                    }
                }
            });
            
            if(playlist.get(genre).size() > 1){
            	answer.addAll(playlist.get(genre).subList(0, 2));
            }else{
                answer.addAll(playlist.get(genre));
            }
        }
        return answer.stream().mapToInt(i->i).toArray();
    }
}

➕ Python 코드

def solution(genres, plays):
    answer = []
    playlist = {}
    playcount = {}
	
    for i in range(len(genres)):  
        playlist.setdefault(genres[i], []).append(i)
        playcount[genres[i]] = playcount.get(genres[i], 0) + plays[i]
    
    sorted_genres = sorted(playcount.keys(),key=lambda x: -playcount[x])
    
    for genre in sorted_genres:
        playlist[genre].sort(key=lambda x : (-plays[x], x))
        answer += playlist[genre][:2]
  
    return answer

➕ 궁금한 내용 및 소감

아이디어는 참 간단하지만, 문제를 잘못 이해해 조금 헤맸다. 나는 장르도 top 2만 선정해서 출력하는 줄 알았는데, 전체 장르에 대해 출력하는 것이라는 걸 나중에 알았다. 문제를 잘 읽어야 함을 다시 한번 깨닫는다.
파이썬은 익숙해서 그런지 엄청 간단하게 풀었지만, 자바는 너무 너무 너무 구현하기 어려웠다. 하나 구현할 때마다 그 방법을 검색해보았던 것 같다. 아직 자바의 자료구조에 익숙하지 않은 게 큰 문제인 것 같아, 내일은 자료구조 정리시간을 가져봐야겠다.
자바는 코드가 너무 길고 복잡한 게 내가 느끼는 단점인데, stream을 사용하면 파이썬과 유사하게 구현이 가능한 것 같다! 이에 대해서도 공부해보면 좋을 것 같다.