[Programmers] 베스트앨범 JAVA

반응형

728x90

[Programmers] 베스트앨범 - LV 3

---

접근

• 해시

---

풀이

해시 카테고리의 문제로 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트앨범을 만드는 문제이다. 노래 수록 기준으로 속한 노래가 많이 재생된 장르를 먼저 찾는다. 가장 많이 재생된 장르라는 것은 해당 장르의 총 재생수를 기준으로 많은 순서대로 수록하게 된다. 장르 내에선 재생수를 기준으로 2 곡을 수록하게 되는데 횟수가 같다면 고유 번호가 낮은 노래를 먼저 수록하면 된다. 

 

뭔가 SQL 문제로 나올만한 내용이긴 한데 해시 카테고리의 문제이고 대충 보면 HashMap을 써야 할 거 같다. 

    private static class Music {
        int index;
        int play;
        
        public Music(int index, int play){
            this.index = index;
            this.play = play;
        }
    }

결과 반환을 노래의 고유 번호 즉 인덱스를 반환해야 하기 때문에 재생 횟수와 고유 번호를 같이 관리하기 위해 클래스를 생성했다. 

    public int[] solution(String[] genres, int[] plays) {
        Map<String, PriorityQueue<Music>> map = new HashMap<>();
        Map<String, Integer> countMap = new HashMap<>();
        
        int n = genres.length;
        
        for(int i = 0; i < n; i++){
            String genre = genres[i];
            int play = plays[i];
            countMap.merge(genre, play, Integer::sum);
            
            if(map.containsKey(genre)){
                map.get(genre).offer(new Music(i, play));
            } else {
                PriorityQueue<Music> pq = new PriorityQueue<>(
                    (a,b) -> {
                        if(a.play != b.play){
                            return b.play - a.play;
                        } else {
                            return a.index - b.index;
                        }
                    }
                );
                pq.offer(new Music(i, play));
                map.put(genre, pq);
            }
        }

해시 문제다 보니 HashMap을 사용하는데 총 재생 횟수를 기록할 map과 장르별로 노래를 담을 map을 한 개씩 사용했다. 노래를 담는 map은 value로 우선순위 큐를 사용했는데 재생 횟수 내림차순과 같은 경우 고유 번호 오름차순으로 정의해 준 뒤 담아줬다. 

	String[] res = countMap.entrySet().stream()
            .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
            .map(Map.Entry::getKey)
            .toArray(String[]::new);
        
        List<Integer> ans = new ArrayList<>();
        int index = 0;
        
        for(String s : res) {
            PriorityQueue<Music> val = map.get(s);
            
            if(!val.isEmpty()){
                ans.add(val.poll().index);
                index++;
            }
            
            if(!val.isEmpty()){
                ans.add(val.poll().index);
                index++;
            }
        }
        
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

stream을 사용해 총 재생 횟수가 많은 장르부터 정렬을 한 뒤 장르만 String 배열로 뽑아주었다. 정렬된 장르순으로 각 장르에서 노래를 2개씩 뽑아 고유 번호만 담은 뒤 다시 stream을 사용해 String 배열로 반환해 주었다. 

int[] answer = new int[map.size() * 2];

처음엔 장르 개수의 2배를 한 크기로 배열을 미리 만들어 둔 뒤 각 위치에 고유 번호를 넣어줬는데 장르에 존재하는 노래가 2개가 되지 않을 수도 있어 통과에 실패했었다. 

---

전체 코드

import java.util.*;

class Solution {
    private static class Music {
        int index;
        int play;
        
        public Music(int index, int play){
            this.index = index;
            this.play = play;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        Map<String, PriorityQueue<Music>> map = new HashMap<>();
        Map<String, Integer> countMap = new HashMap<>();
        
        int n = genres.length;
        
        for(int i = 0; i < n; i++){
            String genre = genres[i];
            int play = plays[i];
            countMap.merge(genre, play, Integer::sum);
            
            if(map.containsKey(genre)){
                map.get(genre).offer(new Music(i, play));
            } else {
                PriorityQueue<Music> pq = new PriorityQueue<>(
                    (a,b) -> {
                        if(a.play != b.play){
                            return b.play - a.play;
                        } else {
                            return a.index - b.index;
                        }
                    }
                );
                pq.offer(new Music(i, play));
                map.put(genre, pq);
            }
        }
        
        String[] res = countMap.entrySet().stream()
            .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
            .map(Map.Entry::getKey)
            .toArray(String[]::new);
        
        List<Integer> ans = new ArrayList<>();
        int index = 0;
        
        for(String s : res) {
            PriorityQueue<Music> val = map.get(s);
            
            if(!val.isEmpty()){
                ans.add(val.poll().index);
                index++;
            }
            
            if(!val.isEmpty()){
                ans.add(val.poll().index);
                index++;
            }
        }
        
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}