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

 

 

사용 알고리즘

• 해쉬

 

풀이

 

기존에 제출해서 틀린 풀이

import java.util.*;
class Solution {
    // 1. 장르의 플레이 타임 총합을 맵에 담아서 많이 재생된 순서로 정렬한다.
    public int[] solution(String[] genres, int[] plays) {

        
        Map<String, Integer> genreMap = new HashMap<>();
        Map<Integer, Integer> indexMap = new HashMap<>();
        
        for(int i = 0; i < genres.length; i++) {
            genreMap.put(genres[i] , genreMap.getOrDefault(genres[i], 0) + plays[i]);
            indexMap.put(i, plays[i]);
        }
        
        List<Integer> totalPlays = new ArrayList<>(genreMap.values());
        
        Collections.sort(totalPlays, Collections.reverseOrder());
        // 플레이 타임이 많은 장르 순서로 정렬
        
        List<Integer> result = new ArrayList<>(); // 결과값
        for(int i = 0; i < totalPlays.size(); i++) {
            
            List<Integer> tmp = new ArrayList<>(); // 장르가 같은 노래들 재생시간을 저장하는 임시 리스트
            for(int j = 0; j < genres.length; j++) {
                if (genreMap.get(genres[j]) == totalPlays.get(i)) {
                    tmp.add(plays[j]);
                }
            }
            
            Collections.sort(tmp, Collections.reverseOrder());
            
            for(int j = 0; j < 2; j++){
                int play = tmp.get(j);
                for(int k = 0; k < indexMap.size(); k++) {
                    if (indexMap.get(k) == play) {
                        result.add(k);
                    }
                }
            }
            
        }
        
        int[] answer = new int[result.size()];
        for(int i = 0; i < answer.length; i++) answer[i] = result.get(i);
        
        return answer;
    }
}

 

테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	통과 (0.32ms, 74.7MB)
테스트 4 〉	실패 (런타임 에러)
테스트 5 〉	통과 (1.37ms, 83.2MB)
테스트 6 〉	통과 (1.09ms, 74.7MB)
테스트 7 〉	통과 (0.58ms, 73.5MB)
테스트 8 〉	실패 (런타임 에러)
테스트 9 〉	실패 (런타임 에러)
테스트 10 〉	통과 (1.22ms, 78.5MB)
테스트 11 〉	실패 (런타임 에러)
테스트 12 〉	실패 (런타임 에러)
테스트 13 〉	통과 (1.19ms, 78.1MB)
테스트 14 〉	통과 (0.82ms, 83.6MB)
테스트 15 〉	실패 (0.31ms, 71.7MB)

 

 

통과 코드

import java.util.*;
class Solution {
    // 1. 장르의 플레이 타임 총합을 맵에 담아서 많이 재생된 순서로 정렬한다.
    public int[] solution(String[] genres, int[] plays) {

        
        Map<String, Integer> genreMap = new HashMap<>();
        
        for(int i = 0; i < genres.length; i++) {
            genreMap.put(genres[i] , genreMap.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        List<String> genreList = new ArrayList<>(genreMap.keySet());
        
        Collections.sort(genreList, (a,b) -> genreMap.get(b) - genreMap.get(a));
        // 플레이 타임이 많은 장르 순서로 정렬
        
        List<Integer> result = new ArrayList<>(); // 결과값

        for(String genre : genreList) {
            Map<Integer,Integer> playsMap = new HashMap<>();
            for(int i = 0; i < genres.length; i++) {
                if (genre.equals(genres[i])) {
                    playsMap.put(i, plays[i]); // 고유번호와 플레이 시간을 할당
                }
            }
            
            List<Integer> playList = new ArrayList<>(playsMap.keySet());
            
            Collections.sort(playList, (a,b) -> playsMap.get(b) - playsMap.get(a));
            
            result.add(playList.get(0));
            if (playList.size() >= 2) {
                result.add(playList.get(1));
            }
        }
                
        int[] answer = new int[result.size()];
        for(int i = 0; i < answer.length; i++) answer[i] = result.get(i);
        return answer;
    }
}

 

회고

 

기존에 풀었던 방식은 임의로 loop를 2까지 돌려서 틀렸다. 

 

그리고, 고유 번호와 재생 시간을 저장할 때

indexMap.put(plays[i], i);

 

재생시간, 고유 번호 순서로 저장을 하게 되면 2,15번 테스트 케이스에서 통과를 하지 못한다. 아무래도 문제에서 3번 조건인

• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

이것을 만족하지 못해서 틀린 것 같다.

 

그리고 오답과 정답의 결정적으로 틀린 부분은, 

List<Integer> tmp = new ArrayList<>(); // 장르가 같은 노래들 재생시간을 저장하는 임시 리스트

Collections.sort(tmp, Collections.reverseOrder());

 

재생시간을 저장해서 내림 차순을 했다면

 

List<Integer> playList = new ArrayList<>(playsMap.keySet());
            
Collections.sort(playList, (a,b) -> playsMap.get(b) - playsMap.get(a));

 

정답에선 playsMap의 keySet, 즉 고유 번호를 가지는 리스트를 만들고 고유 번호에 해당하는 재생 수에 대해서 내림차순을 했다.

 

이렇게 되면,

고유번호 2, 재생 시간 500

고유번호 3, 재생 시간 500 

 

이렇게 재생시간이 같더라도 2,3 순서로 고유 번호가 작은 순서로 정렬되기 때문에 원하는 답을 찾을 수 있다.

 

keySet을 기준으로 리스트를 만들고 value 값으로 정렬하는 것을 생각하자!!!