[알고리즘/자바] 프로그래머스 - 베스트 앨범

 

 

 

 

코딩테스트 연습 - 베스트앨범

 

생각보다 신경써줘야 할게 많아서 힘들었다. 반례(테스트케이스) 관련 링크는 제일 하단에 있다.

 

 나는 먼저 key를 장르, value를 장르 재생횟수의 총합으로 가지는 HashMap을 만들었다. ( genres_sum ) 

그리고 max_genres라는 함수를 통해 현재 genres_sum에서 가장 재생횟수가 많은 장르를 return 하도록 했다.

 

이제부터 while을 돌며 앨범을 만들면된다.

max_genres함수를 통해 가장 재생횟수가 많은 장르를 가져왔다면 plays에서 해당 장르에 대한 재생횟수 정보를 가져온다.

가져온 재생횟수 정보를 내림차순으로 정렬하고 가장큰 2개를 가져오면 된다. ( 물론 2개가 없다면 1개. ) 

여기까지 작업을 완료하면 genres_sum에서 장르를 삭제한다. 

이 작업을 genres_sum이 빌때까지 한다. 

 

 

import java.util.*;

class Solution {
    
    public static String max_genres(HashMap<String,Integer> genres_sum) {
		int max_value = 0;
		String max_key ="";
		
		for( Map.Entry<String, Integer> elem : genres_sum.entrySet() ){
			
	        if ( elem.getValue() >= max_value) {
	        	max_value = elem.getValue();
	        	max_key = elem.getKey();
	        }
			
	      }
		return max_key;

	}
    
    
    
    
    public int[] solution(String[] genres, int[] plays) {
        
        int[] answer = {};
				
		// 장르별 합계
		HashMap<String,Integer> genres_sum = new HashMap<String,Integer>();
		// 총합이 큰 장르의 plays
		ArrayList<Integer> max_genre_list = new ArrayList<Integer>();
		// 정답.
		ArrayList<Integer> ans = new ArrayList<Integer>();
		
		
		// 장르별 총합. ( HashMap )
		for(int i=0; i<genres.length; i++) {
			if(genres_sum.containsKey(genres[i])) {
				int tmp = genres_sum.get(genres[i]);
				genres_sum.put(genres[i], tmp+plays[i]);
			}
			else {
				genres_sum.put(genres[i], plays[i]);
			}
		}
		
		// 앨범만들기 시작.
		while(true) {
			
			// 뽑을 곡이 없는 경우 종료.
			if( genres_sum.isEmpty()) {
				answer = ans.stream().mapToInt(i -> i).toArray();
				break;
			}
			else {
				
				max_genre_list.clear();

				// 총합이 가장큰 장르 가져옴.
				String m_genre = max_genres(genres_sum);
				
				// m_genre 장르에 해당하는 재생횟수 가져오기.
				int [] t_plays = plays.clone();
				for(int i = 0 ; i< genres.length; i++ ) {
					
					// 총합이 가장큰 장르의 값들을 저장
					if( genres[i].equals(m_genre) ) {
						max_genre_list.add(t_plays[i]);
					}
					// 그 외 장르는 재생횟수를 0으로.
					else {
						
						t_plays[i] = -1;
					}
				}

				
				// 가져온 장르의 재생횟수를 내림차순으로 정렬한다.
				Collections.sort(max_genre_list);
				Collections.reverse(max_genre_list);
				

				ArrayList<Integer> t_plays_list = new ArrayList<Integer>();
				for(int p : t_plays)t_plays_list.add(p);
				
				
				// 가장큰값 2개 가져오기. 없으면 1개만.
				for(int j = 0; j<max_genre_list.size(); j++) {
					
					if( j > 1 ) {
						break;
					}
					 
					int p = t_plays_list.indexOf(max_genre_list.get(j));
					
					// 재생횟수가 같은경우를 위해 꺼낸 곡은 -1 처리
					t_plays_list.set(p, -1);
					ans.add(p);
				}
				
				// 처리한 장르는 총합목록에서 제거.
				genres_sum.remove(m_genre);

			}

		}

        return answer;
        
        
    }
}

 

반례는 한 유저분이 잘 정리해두셨다. 

https://programmers.co.kr/learn/questions/7468

테스트 케이스 관련 도움 요청드립니다.