[프로그래머스/JAVA] 베스트 앨범 - 해시

 

먼저 생각했던 풀이 방법은 아래와 같다.

• 각 장르의 개수를 HashMap에 담기

classic : 3
pop : 2

 

• 각 장르의 재생 횟수 합계를 HashMap에 담고, 내림차순으로  sorting하기

pop : 3100
classic : 1450

pop 장르의 재생 횟수 합계가 가장 많으므로 pop 장르 노래의 index가 먼저 수록되어야 한다.  ex) 4, 1

그 다음으론 classic 장르 노래의 index가 수록되어야 하는데 각 장르별 2개씩만 수록될 수 있으므로 3, 0이 차례로 수록되고 2는 수록되지 못한다. 따라서 앨범엔 4, 1, 3, 0 index 순으로 수록된다.

 

이를 위하여 HashMap<String, HashMap<Integer, Integer>> hm = new HashMap<String, HashMap<Integer, Integer>>(); 를 생성하였다. 

key는 장르이며, value가 또 HashMap인데 이 HashMap의 key는 재생횟수이며, value는 해당 재생횟수의 index이다.

재생횟수 합계가 높은 장르의 모든 재생횟수와 각 재생횟수의 index를 넣기 위함이였다. 그리고 이 후에 inner? HashMap을 내림차순 sorting해주며, 상위 2개의 index(value)만 resultList에 넣어주었다. (1개만 있는 경우는 1개만 넣어줌)

 

public int[] solution(String[] genres, int[] plays) {
        
    	//각 장르의 개수
        HashMap<String, Integer> genreCntMap = new HashMap<String, Integer>();
        for (int i=0; i<genres.length; i++) {
        	genreCntMap.put(genres[i], genreCntMap.getOrDefault(genres[i], 0)+1);
        }
        
        //각 장르의 재생 횟수 합계
        HashMap<String, Integer> genreSumMap = new HashMap<String, Integer>();
        for (int i=0; i<genres.length; i++) {
        	genreSumMap.put(genres[i], genreSumMap.getOrDefault(genres[i], 0)+plays[i]);
        }
        
       
        List<Entry<String, Integer>> listEntries = new ArrayList<Entry<String, Integer>>(genreSumMap.entrySet());

        Collections.sort(listEntries, new Comparator<Entry<String, Integer>>() {
			
			@Override
			public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2) {
				// 내림차순 정렬
				return obj2.getValue().compareTo(obj1.getValue());
			}
		});
		
        
		HashMap<String, HashMap<Integer, Integer>> hm = new HashMap<String, HashMap<Integer, Integer>>();
		
		for (int i=0; i<genres.length; i++) {
			
			HashMap<Integer, Integer> value = null;
			if(hm.containsKey(genres[i])) {
				value = hm.get(genres[i]);
			}else {
				value = new HashMap<Integer, Integer>();
			}
			value.put(plays[i], i);
			hm.put(genres[i], value);
        	
        }
        
		
		List<Integer> result = new ArrayList<>();
		for(Entry<String, Integer> entry : listEntries) {
			
			
			List<Entry<Integer, Integer>> order = new ArrayList<Entry<Integer, Integer>>(hm.get(entry.getKey()).entrySet());

			Collections.sort(order, new Comparator<Entry<Integer, Integer>>() {
				
				@Override
				public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
					// 내림차순 정렬
					return obj2.getKey().compareTo(obj1.getKey());
				}
			});
			
			result.add(order.get(0).getValue());
			if(genreCntMap.get(entry.getKey()) != 1) {
				result.add(order.get(1).getValue());
			}
			
		}
		
		int[] i = result.stream().mapToInt(Integer::intValue).toArray();
    
        return  i;
    }

 

예제는 원하는 결과대로 나왔지만 다른 테스트 케이스에서 실패하였다....

그리고 테스트가 모두 성공해도 효율성 테스트에서 막힐거라고 생각은 하고 있었다. 내가 생각해도 복잡했기에!

---

 각 장르의 개수를 HashMap에 담을 필요가 없을 것 같아 제외시켰고, HashMap<String, HashMap<Integer, Integer>> 부분이 너무 복잡하다고 생각해서 Music이라는 class를 생성하고 List<Music> resultList로 바꿔주었다.

class Music{
	String genres;
	int plays;
	int index;
	
	public Music(String genres, int plays, int index) {
		this.genres=genres;
		this.plays=plays;
		this.index=index;
	}
}

 

최종 소스는 아래와 같다.

public int[] solution(String[] genres, int[] plays) {
    	int[] answer = {};
    	 
        //각 장르의 재생 횟수 합계
        HashMap<String, Integer> genreSumMap = new HashMap<String, Integer>();
        for (int i=0; i<genres.length; i++) {
        	genreSumMap.put(genres[i], genreSumMap.getOrDefault(genres[i], 0)+plays[i]);
        }
        
       
        List<Entry<String, Integer>> listEntries = new ArrayList<Entry<String, Integer>>(genreSumMap.entrySet());
        
        Collections.sort(listEntries, new Comparator<Entry<String, Integer>>() {
	
			@Override
			public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2) {
				//내림차순 정렬 
				return obj2.getValue().compareTo(obj1.getValue()); // 내림차순
			}
		});
		
		List<Music> resultList = new ArrayList<Music>();
		for (int i=0; i<listEntries.size(); i++) {
			List<Music> tempList = new ArrayList<Music>();
			
			
			for(int j=0; j<genres.length; j++) {
				if(listEntries.get(i).getKey().equals(genres[j])) {
					tempList.add(new Music(genres[j], plays[j], j));
				}
			}
			
			Collections.sort(tempList, new Comparator<Music>() {

				@Override
				public int compare(Music o1, Music o2) {
					//내림차순 정렬 
					return o2.plays - o1.plays;
				}
			});
			
			resultList.add(tempList.get(0));
			if(tempList.size() != 1 ) {
				resultList.add(tempList.get(1));
			}
		}
		
		answer = new int[resultList.size()];
		for(int i=0; i<resultList.size(); i++) {
			answer[i] = resultList.get(i).index;
		}
		return answer;
    }