[프로그래머스] 베스트앨범 문제 (Java Hash 풀이)

안녕하세요, 스코리아입니다.

오늘은 자바(Java)의 Hash(해시)를 이용한 프로그래머스 Lv.3 베스트앨범 문제를 풀어보겠습니다.

이 문제는 풀이 방식이 너무나도 다양하기 때문에, 풀이의 효율을 따지기가 조금 애매한 부분이 있습니다. 감안하고 봐주시기 바랍니다.

 

문제 설명

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

프로그래머스

노래를 수록하는 기준을 고려하여, 노래가 들어간 순서대로 고유 번호를 출력하는 문제입니다.

genres = 장르, plays = 노래 재생 횟수, 고유번호 = plays의 0부터 시작하는 순서

 

노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. (genres 장르 내의 모든 노래 재생 횟수를 합쳐서, 높은 장르 순서대로)
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

• 모든 장르는 재생된 횟수가 다릅니다. (1) 기준에서 높은 장르 순서대로 정렬할 때 겹치는 장르가 없다는 뜻입니다.
• 장르별로 최대 두 개씩만 수록해야 합니다.

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

문제에 나와있는 예시를 토대로 설명해 보겠습니다.

genres (장르)	plays (재생 횟수)	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

1. (1) 기준을 먼저 적용하기 위해, 각 장르별로 총 재생 횟수를 계산합니다.

• classic : 500 + 150 + 800 = 1,450회
• pop: 600 + 2500 = 3,100회

2. 높은 재생 순서대로 수록되어야 하므로, pop이 먼저 수록되고 classic이 다음으로 수록되어야 합니다.

3. pop 수록하기

• 고유 번호 1: 600회 재생
• 고유 번호 4: 2500회 재생

4. (2) 기준에 따라, 고유 번호 4->1 순서로 수록합니다. 

5. class 수록하기

• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생
• 고유 번호 3: 800회 재생

6. (2) 기준에 따라 고유번호 3->0 순서로 수록합니다. 장르별로 최대 2개씩만 수록할 수 있으므로 2는 수록하지 못합니다.

---

풀이 과정 - 1번

저는 문제의 취지에 맞게, Hash와 List를 사용하여 문제를 풀어보았습니다.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<String, HashMap<Integer, Integer>> map2 = new HashMap<>();
        for(int i=0;i<genres.length;i++){
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
            HashMap<Integer, Integer> hashMap = map2.getOrDefault(genres[i], new HashMap<>());
            hashMap.put(i, plays[i]);
            map2.put(genres[i], hashMap);
        }
        
        // 장르 오름차순 정렬
        List<String> sortedGenres = new ArrayList<>(map.keySet());
        sortedGenres.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
        
        for(String p : sortedGenres){
            HashMap<Integer, Integer> m = map2.get(p);
            
            int count = 0;
            
            // 노래 재생 횟수 오름차순 정렬
            List<Integer> sortedSongs = new ArrayList<>(m.keySet());
            sortedSongs.sort((o1, o2) -> m.get(o2).compareTo(m.get(o1)));
            
            for(Integer s : sortedSongs){
                if(count == 2){
                    break;
                }
                answer.add(s);
                count++;
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

1. answer 배열에는 몇 개의 데이터가 들어갈지 예상할 수 없기 때문에, ArrayList를 사용하였습니다.
2. map : 장르별 장르내 총 재생 횟수를 뜻합니다. key 값에는 genres(장르)가, value에는 재생 횟수가 들어갑니다.
3. map2: 장르별 노래목록을 뜻합니다. key 값은 genres(장르)가, value에는 또 다른 Map으로 key에는 해당 노래의 index(고유번호)가, value에는 노래 재생 횟수(plays)가 들어갑니다.
4. 위의 예제를 예시로 든다면, map에는 ["classic" : 1450, "pop": 3100]가 될 것이고, map2에는 ["classic" : {[0, 500], [2, 150], [3,800]}, "pop":{[1, 600], [4, 2500]}] 이 될 것입니다.
5. 장르별 장르내 총 재생 횟수인 map을 오름차순으로 정렬합니다. 재생 횟수가 높은 장르부터 먼저 수록되어야 하기 때문입니다.
6. 정렬한 sortedGenres을 for문 돌려서 map2에서 해당 장르의 노래들을 가져옵니다. (m)
7. 노래 재생 횟수인 m의 value 값을 기준으로 오름차순으로 정렬합니다. 재생 횟수가 높은 노래부터 먼저 수록되어야 하기 때문입니다.
8. 정렬한 sortedSongs을 for문 돌려서 장르내 최대 2개까지 등록합니다. answer.add(s);
9. 모든 for문이 탈출되면, answer List를 int array로 바꿔서, return 합니다.

실행 결과 - 1번

프로그래머스 문제 실행결과 (1) - 베스트앨범

• 대부분의 테스트는 3~6ms 정도로, 그렇게 빠르지는 않습니다.
• 뭐가 문제일까요?
• 제가 파악한 결과,. sort()를 이용하여 hash의 value를 기준으로 오름차순으로 정렬하는 부분에서 많은 시간이 소비된 것으로 확인하였습니다.

---

풀이 과정 - 2번

위의 문제를 해결하기 위해 정렬 부분을 수정하여 조금 더 실행 속도를 올려보겠습니다.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<String, HashMap<Integer, Integer>> map2 = new HashMap<>();
        for(int i=0;i<genres.length;i++){
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
            HashMap<Integer, Integer> hashMap = map2.getOrDefault(genres[i], new HashMap<>());
            hashMap.put(i, plays[i]);
            map2.put(genres[i], hashMap);
        }

	// 장르 오름차순 정렬 (.sort() 없이 직접 돌리기)
        List<String> sortedGenres = new ArrayList<>();
        while(map.size() != 0){
            int max = 0;
            String max_k = "";
            for(String k : map.keySet()){
                if(max < map.get(k)){
                    max = map.get(k);
                    max_k = k;
                }
            }
            sortedGenres.add(max_k);
            map.remove(max_k);
        }
        
        for(String p : sortedGenres){
            HashMap<Integer, Integer> m = map2.get(p);
            
            int count = 0;
            
            // 노래 재생 횟수 오름차순 정렬 (.sort() 없이 직접 돌리기)
            while(m.size() != 0 && count < 2){
                int max = 0;
                int max_k = 0;
                for(Integer k : m.keySet()){
                    if(max < m.get(k)){
                        max = m.get(k);
                        max_k = k;
                    }
                }
                answer.add(max_k);
                m.remove(max_k);
                count++;
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

• . sort()를 사용하지 않고, while 문과 for문을 사용하여 정렬을 진행하였습니다.

실행 결과 - 2번

프로그래머스 문제 실행결과 (2) - 베스트앨범

• 대부분의 테스트는 2~3ms 정도로, 비교적 빠른 모습입니다.
• 1번 풀이보다 1~5ms 정도 빠릅니다.

---

이번 문제는 프로그래머스 Lv.3 답게 HashMap, List, 정렬 등이 섞인 복합 문제라고 생각합니다.

지금까지 자바(Java) 해시를 이용한 프로그래머스 '베스트앨범' 문제에 대해서 알아보았습니다.

 

읽어주셔서 감사합니다.