[프로그래머스] 베스트 앨범 [JAVA]

출처 : programmers.co.kr/learn/courses/30/lessons/42579#

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

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres                                            plays                                               return

[classic, pop, classic, classic, pop]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

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

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

전체 코드

import java.util.*;
import java.util.Map.Entry;
class Solution {
    
    static int[] genre_count;
    static HashMap<String, Integer> indexing ;
    static ArrayList< ArrayList<Music> > arr;
    static ArrayList< Integer > solve ;
    
    public static class Music implements Comparable<Music>{
        int count;
        int index;
        
        public Music(int count, int index){
            this.count = count;
            this.index = index;
        }
        
        @Override
        public int compareTo(Music o){
            if( this.count < o.count ){
                return 1;
            }
            else if ( this.count > o.count){
                return -1;
            }
            else {
                return this.index - o.index;
            }
            
        }

		@Override
		public String toString() {
			return " Music [count=" + count + ", index=" + index + "]";
		}
        
    }
    // Todo: 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범 출시하기
    public static int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        
        indexing = new HashMap<>();
        arr =  new ArrayList< ArrayList<Music>>();
        solve = new ArrayList<Integer>();
        
        int size =0; 
        for( int i=0; i<genres.length; i++){
            String G = genres[i];
            int P = plays[i];
            
            // 저장되어 있지 않다면 새로 추가해주고
            if (!indexing.containsKey(G)) {
            	indexing.put(G, size);
            	arr.add(new ArrayList<Music>());
            	arr.get(size).add( new Music( P, i));
            	size++;
            	
            } 
            // 저장되어 있다면, 해당 index에 추가해주기
            else {
            	
            	arr.get( indexing.get(G )).add( new Music( P, i)); 
            }
                         
        }
        System.out.println(size);
        // Hash test
        for( Entry<String, Integer> HS : indexing.entrySet()) {
        	System.out.println( HS.getKey() + "/ index : " + HS.getValue());
        }
        
        
        
        // arr Test
        for( int i=0; i<arr.size(); i++) {
        	Collections.sort(arr.get(i));
        	for( int j=0; j<arr.get(i).size(); j++) {
        		System.out.print(arr.get(i).get(j).toString());
        	}
        	System.out.println();
        }
        
        genre_count = new int[size];
        
        // 1. 가장 많이 재생된 장르 먼저 수록 
        // 먼저 순서대로 정렬하기
        for( int i=0; i<arr.size(); i++) {
        	for( int j=0; j<arr.get(i).size(); j++) {
        		genre_count[ i ] += arr.get(i).get(j).count;
        	}
        }
        
        for( int tmp : genre_count) {
        	System.out.println("count : " + tmp );
        }
        
        
        // 총합이니까, HashMap 통해서 재생회수 index 가리키게 => 순서 정렬하기 
        int[] rank = new int[size];
        
        for( int i=0; i<rank.length; i++) { // 2
        	int max = Integer.MIN_VALUE;
        	for( int j=0; j<rank.length; j++) {
        		if( max < genre_count[j] ) {
        			max = genre_count[j];
        		}
        	} // 1
        	
        	for( int j=0; j<rank.length; j++) {
        		// 최대값 순서대로
        		if ( max == genre_count[j]) {
        			genre_count[j] = Integer.MIN_VALUE; // 최소값으로 바꿔주기
        			// solve에 하나씩 넣어주자.
        			if ( arr.get(j).size() == 1 ) {
        				solve.add( arr.get(j).get(0).index);
        			} else { // 2개 넣기
        				solve.add( arr.get(j).get(0).index);
        				solve.add( arr.get(j).get(1).index);
        			}
        			
        		}
        	}
        }
        answer = new int[solve.size()];
        for( int i=0; i<solve.size(); i++) {
        	answer[i] = solve.get(i);
        }
        
        // 2. 해당 장르 내에서 많이 재생된 노래를 먼저 수록 
        // 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
        // - 우선순위 큐  - 2개 ArrayList로 관리 ( 고유 번호 -> index 작은 것 부터)
        
        
        return answer;
    }
}

문제 풀이

1. HashMap 은 장르 - genre_count [ Indexing ] ,
                              arr [ Indexing ] 
   즉, Index 가리키는 용도로 사용하였다.

2. ArrayList< ArrayList< Music > > arr   <-- 2차원 링크드 리스트 
    즉, 해당 index에 재생 횟수,  고유 번호 i 가 저장 되어 있다.

  ex.

3. 추가적으로 arr 을 조건 2, 조건 3에 맞게 우선순위 정렬을 해주었다. ( 관련 코드 ) 
 - Collections.sort( arr.get(i));

public static class Music implements Comparable<Music>{
        int count;
        int index;
        
        public Music(int count, int index){
            this.count = count;
            this.index = index;
        }
        
        @Override
        public int compareTo(Music o){
            if( this.count < o.count ){
                return 1;
            }
            else if ( this.count > o.count){
                return -1;
            }
            else {
                return this.index - o.index;
            }
            
        }

		@Override
		public String toString() {
			return " Music [count=" + count + ", index=" + index + "]";
		}
        
    }

 for( int i=0; i<arr.size(); i++) {
        	Collections.sort(arr.get(i));
        	for( int j=0; j<arr.get(i).size(); j++) {
        		System.out.print(arr.get(i).get(j).toString());
        	}
        	System.out.println();
        }

4. 각 arr에 연결된 값들의 합을 genre_count 에 저장해두기

 for( int i=0; i<arr.size(); i++) {
        	for( int j=0; j<arr.get(i).size(); j++) {
        		genre_count[ i ] += arr.get(i).get(j).count;
        	}
        }

5. 가장 큰 값 부터 index로 사용하면서 arr에 담아두기

 for( int i=0; i<genre_count.length; i++) { // 2
        	int max = Integer.MIN_VALUE;
        	for( int j=0; j<genre_count.length; j++) {
        		if( max < genre_count[j] ) {
        			max = genre_count[j];
        		}
        	} // 1
        	
        	for( int j=0; j<genre_count.length; j++) {
        		// 최대값 순서대로
        		if ( max == genre_count[j]) {
        			genre_count[j] = Integer.MIN_VALUE; // 최소값으로 바꿔주기
        			// solve에 하나씩 넣어주자.
        			if ( arr.get(j).size() == 1 ) {
        				solve.add( arr.get(j).get(0).index);
        			} else { // 2개 넣기
        				solve.add( arr.get(j).get(0).index);
        				solve.add( arr.get(j).get(1).index);
        			}
        			
        		}
        	}
        }
        answer = new int[solve.size()];
        for( int i=0; i<solve.size(); i++) {
        	answer[i] = solve.get(i);
        }

배운 점

1. ArrayList를 계속 2중 ArrayList 모양처럼 동적으로 구현할 수 있음.

2. test를 하며 Entry < String , Integer > : entrySet ( 저장된 값 확인 가능 ) 

느낀 점

1. 문제는 안어려운데 코드 짜는데 불필요한 시간들이 너무 많이 소요 되었다. 또한, 코드도 매우 비효율적으로 보임

2. indexing 해시로 index 값을 정해버려서 정렬하기가 매우 까다롭다. 어떻게 할까?