1. 문제 설명

• 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시

문제 조건

• 속한 노래가 많이 재생된 장르를 먼저 수록함. (장르별 재생 횟수 내림차순)
• 장르 내에서 많이 재생된 노래를 먼저 수록함. (노래 재생 횟수 내림차순)
• 장르 내에서 재생 횟수가 같은 노래들은 고유 번호가 낮은 노래를 먼저 수록함.(재생 횟수 비교 -> 노래 id 비교)

genres: ["classic", "pop", "classic", "classic", "pop"]	
plays:	[500, 600, 150, 800, 2500]
return: [4, 1, 3, 0]

2. 스크래치

풀이: 해시맵 (Hash Map)

0) Song 클래스 정의

1) [for문] 장르별 총 재생 횟수 & 각 장르별 노래 목록 정리 (장르 내부 정렬)

• 장르별 총 재생수 계산
  genrePlayMap: Map<String, Integer> 타입에 <장르, 재생 횟수> 값 담기
• 장르별 노래 목록 정렬
  genrePQMap: Map<String, PriorityQueue<Song> 타입에 <장르, 장르별 노래 목록의 PQ> 값 담기

2) 장르 순서 정렬 (장르 <-> 장르)

• genrePlayMap의 keySet을 통해 장르들의 키 값을 ArrayList로 감싸 List<String> genreOrder에 담기
• sort 함수를 통해 내림차순하여 인기 장르부터 순서대로 정렬

3) 장르 순서대로 상위 2곡씩 꺼내기

• 결과를 담을 List<Integer> result 선언
• List<String> genreOrder를 for문으로 순회하며 각 장르의 pq에서 2번씩 poll
• List<Integer> result를 stream을 통해 int[] 배열로 만들기
  
  

3. 코드

import java.util.*;

class Solution {

    // 0. Song 클래스 정의 
    static class Song {
        int id;
        int plays;

        Song(int id, int plays) {
            this.id = id;
            this.plays = plays;
        }
    }

    public int[] solution(String[] genres, int[] plays) {

        Map<String, Integer> genrePlayMap = new HashMap<>();
        Map<String, PriorityQueue<Song>> genrePQMap = new HashMap<>();

        // 1. 장르별 총 재생수 & 곡 리스트 구성 
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int playCount = plays[i];

            // 장르별 총 재생수 관리
            if (genrePlayMap.containsKey(genre)) {
                int currentTotal = genrePlayMap.get(genre);
                genrePlayMap.put(genre, currentTotal + playCount);
            } else {
                genrePlayMap.put(genre, playCount);
            }

            // 장르별 PQ가 없다면 만들기
            if (!genrePQMap.containsKey(genre)) {
                genrePQMap.put(genre, new PriorityQueue<>(
                    (s1, s2) -> {
                        if (s1.plays == s2.plays) return s1.id - s2.id; // id 오름차순
                        return s2.plays - s1.plays;                     // plays 내림차순
                    }
                ));
            }

            // 있다면 장르별 PQ에 곡 추가
            genrePQMap.get(genre).offer(new Song(i, playCount));
        }

        // 2. 장르 정렬 (총 재생수 내림차순)
        List<String> genreOrder = new ArrayList<>(genrePlayMap.keySet());
        genreOrder.sort((a, b) -> genrePlayMap.get(b) - genrePlayMap.get(a));


        // 3. PQ에서 상위 곡 2개만 꺼내기
        List<Integer> result = new ArrayList<>();

        for (String g : genreOrder) {
            PriorityQueue<Song> pq = genrePQMap.get(g);

            if (!pq.isEmpty()) result.add(pq.poll().id);
            if (!pq.isEmpty()) result.add(pq.poll().id);
        }

        // [output]
        return result.stream().mapToInt(i -> i).toArray();
    }
}

4. De-fault

시간 복잡도

단계	복잡도
장르별 총 재생수 계산	O(N)
장르별 PQ 삽입	O(N log N)
장르 정렬	O(G log G) (G = 장르 개수)
각 장르에서 곡 2개 선택	O(G log N)
총합	O(N log N)

TIL

1) 람다식을 통한 Comparator 작성

• PriorityQueue, List 정렬 등 Comparator 사용 시 람다식 작성을 통해 가독성을 높임.

// 기존 방식
Comparator<Integer> comp = new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return b - a;
    }
};

// 람다식 방식
Comparator<Integer> comp = (a, b) -> b - a;

2) Stream을 통한 타입 변환

• Stream API는 컬렉션 데이터를 처리하는 파이프라인 기능임.
• 문제에서 List<Integer> -> int[] 타입 변환

return result.stream()
             .mapToInt(i -> i)
             .toArray();

• 리스트를 스트림으로 변환한 후

• Integer 객체를 기본 int로 언박싱하여 (IntStream 생성)

• toArray()를 통해 IntStream을 int[]로 변환함.

  
  

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂