[Java] 베스트앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=java

문제설명

가장 많이 재생된 2곡 모아 베스트앨범 출시.
노래는 고유번호로 구분

<노래를 수록하는 기준>
1. 속한 노래가 많이 재생된 장르
2. 장르 내 많이 재생된 노래를 먼저 수록
3. 장르 내에서 재생 횟수가 같은 노래 중 고유번호가 낮은 노래를 먼저 수록

제한사항

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

입출력 예

classic: 500+150+800 = 1450회 재생

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

pop: 600+ 2500 = 3100번 재생

• 고유 번호 1번: 600번
• 고유 번호 4번: 2500번

따라서 pop 장르의 4번 , 1번 / classic 장르의 3번, 0번 수록(장르별 최대 2개까지)

-> [4, 1, 3, 0] return

초기 생각(인덱스가 아닌 재생횟수를 출력해버림)

1. HashMap 2개 생성:
   1. idxMap: key-장르의 인덱스값, value-재생횟수
   2. genMap: key-장르 종류, value-재생횟수 합
2. 기준1-가장 많이 재생된 장르 -> 2번째 hashMap의 values를 내림차순 정렬한 key값
3. 기준2-장르에서 가장 많이 재생된 노래-> 2번째 hashMap의 value를 1번째 hashMap의 value 중 일치하는 key값을 가져온다(2번만 시행). 이때, 장르 내 재생횟수가 같다면, 고유번호가 낮은 번호부터 answer에 넣기.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        int[] answer = {};
        
        // 1. HashMap 생성
        HashMap<Integer, Integer> idxMap = new HashMap<>();
        HashMap<String, List<Integer>> genMap = new HashMap<>();
        
        for(int i=0; i<genres.length; i++){
            // 곡 인덱스 별= 재생 수 저장
            idxMap.put(i, plays[i]);
            // 장르 별= [재생 수] 리스트 저장
            genMap.putIfAbsent(genres[i], new ArrayList<>() ); // 장르가 없으면 새 리스트 추가
            genMap.get(genres[i]).add(plays[i]);
        }
        // System.out.println("genMap: "+genMap);
        
        // 2. 기준 1: 가장 많이 재생된 장르 찾기
        // 장르별 재생수 합을 기준으로 정렬
        ArrayList<String> sortedGen = new ArrayList<>(genMap.keySet());
        
        sortedGen.sort((g1, g2)->{
            int total1 = genMap.get(g1).stream().mapToInt(Integer::intValue).sum();
            int total2 = genMap.get(g2).stream().mapToInt(Integer::intValue).sum();
            return Integer.compare(total2, total1); // 내림차순 정렬
        });
        
        // System.out.println("sortedGen: "+sortedGen);

        // 3. 기준 2: 장르내 가장 많이 재생된 노래
        List<Integer> result = new ArrayList<>();
        
        for(String genre: sortedGen){
            // 장르의 노래 재생 수 기준으로 내림차순 정렬
            List<Integer> song= genMap.get(genre);
            song.sort(Comparator.reverseOrder()); // 내림차순 정렬
            
            // 상위 2곡만 선정(but, 2곡이 없을 경우: 곡 수, 2-> 둘 중 최솟값으로)
            for(int i=0; i< Math.min(song.size(), 2); i++){
                result.add(song.get(i));
            }
        }
        
        // 결과 -> 배열로 변환
        answer = result.stream().mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
}

2차 생각(정답)

굳이 해시맵 2개 생성하지 않고,

1. genMap에 인덱스, 재생횟수 함께 저장

• genMap: 장르를 key로 하는 해시맵에 key로 {인덱스, 재생횟수}를 함께 저장하자!

2. 장르 내에서 정렬 후 인덱스 추출

• plays 배열에서 재생수 기준으로 정렬하되, 같은 재생수라면 인덱스를 기준으로 정렬해야 함.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        int[] answer = {};
        
        // 1. HashMap 생성
        HashMap<String, List<int[]>> genMap = new HashMap<>();
        
        for(int i=0; i<genres.length; i++){
            // 장르가 없으면 새 리스트 추가
            genMap.putIfAbsent(genres[i], new ArrayList<>() ); 
            genMap.get(genres[i]).add(new int[]{plays[i], i}); // [재생수, 인덱스 저장]
        }
        
        // 2. 기준 1: 가장 많이 재생된 장르 찾기
        // 장르별 재생수 합을 기준으로 정렬
        ArrayList<String> sortedGen = new ArrayList<>(genMap.keySet());
        
        sortedGen.sort((g1, g2)->{
            int total1 = genMap.get(g1).stream().mapToInt(arr->arr[0]).sum();
            int total2 = genMap.get(g2).stream().mapToInt(arr->arr[0]).sum();
            return Integer.compare(total2, total1); // 내림차순 정렬
        });
        
        // 3. 기준 2: 장르내 가장 많이 재생된 노래
        List<Integer> result = new ArrayList<>();
        
        for(String genre: sortedGen){
            List<int[]> song= genMap.get(genre);
            
            song.sort((s1, s2)->{
                if(s1[0]==s2[0]){ // 재생수 같다면 고유번호 오름차순 정렬
                    return Integer.compare(s1[1], s2[1]);
                }
                return Integer.compare(s2[0], s1[0]); // 재생수 기준 내림차순
            });
            
            // 상위 2곡만 선정(but, 2곡이 없을 경우: 곡 수, 2-> 둘 중 최솟값으로)
            for(int i=0; i< Math.min(song.size(), 2); i++){
                result.add(song.get(i)[1]); // 인덱스 추가
            }
        }
        
        // 결과 -> 배열로 변환
        answer = result.stream().mapToInt(i->i).toArray();
        
        return answer;
    }
}

사용한 주요 메서드

1. List.sort(Comparator)

• 복잡한 정렬 조건 구현
• 문제에선, song 리스트 정렬용
• Comparator를 람다 표현식으로 구현
• 재생수 기준 내림차순-> 재생수 같을 경우 인덱스 오름차순
• song은 [재생수, 인덱스] 형태의 배열임!

song.sort((s1, s2)->{
	if(s1[0]==s2[0]){
    	return Integer.compare(s1[1], s2[1]);
    }
    return Integer.compare(s2[0], s1[0]);
});

2. List.get(i)[j]

• List의 i번째 요소가 배열일때 해당 배열의 j번째 요소에 접근
• 2차원 List 접근 시 사용

List<int[]> list = new ArrayList<>();
list.add(new int[]{1, 2, 3});
list.add(new int[]{4, 5, 6});

int value = list.get(0)[1]; // 2를 반환
System.out.println(value); // 출력: 2

int anotherValue = list.get(1)[2]; // 6을 반환
System.out.println(anotherValue); // 출력: 6

3. result.stream().mapToInt(i -> i).toArray()

• List타입의 result를 stream으로 변환
• mapToInt(i->i):
  - 스트림의 각 요소(i)를 int로 변환
  - 해당 경우, 이미 요소가 Integer 타입이므로 값만 추출
• toArray():
  - 스트림의 요소를 배열로 변환.
  - 결과: int[]