[프로그래머스] 베스트앨범 (Hash)

문제 소개

오늘 풀었던 프로그래머스 - 베스트앨범 문제를 정리합니다.

이 문제는 장르별로 가장 많이 재생된 노래를 2개씩 뽑아, 전체 재생 수가 많은 장르 순으로 베스트 앨범을 만드는 문제입니다.
정렬과 필터링을 올바르게 설계하는 것이 핵심입니다.

문제 링크: 베스트앨범 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. Music 객체 생성
   • 각 노래를 장르, 재생 수, 고유 번호로 래핑
2. 장르별 그룹핑
   • Collectors.groupingBy()를 통해 장르별 리스트로 묶기
3. 장르 총 재생 수로 정렬
   • entrySet()을 sum(재생 수) 기준으로 내림차순 정렬
4. 각 장르별로 최대 2곡 선택
   • 같은 장르 내에서 재생 수 → 고유 번호 기준으로 정렬 후 2개 선택

---

해결 과정 및 코드

핵심 아이디어

1. Comparable 구현을 통해 재생 수 내림차순 → 고유 번호 오름차순 기준 정렬
2. Map<String, List<Music>> 구조로 장르별 곡을 관리
3. 각 장르에 대해 곡을 정렬 후 최대 2개만 추출

코드

시간 복잡도 : O(N log N) ( 그룹핑 + 정렬 + 누적 => 정렬)

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {

  // Music 클래스: 한 곡의 정보를 담는 객체. Comparable을 구현하여 정렬 기준 지정
  public class Music implements Comparable<Music> {
    private int played;     // 재생 횟수
    private int id;         // 고유 번호 (인덱스)
    private String genre;   // 장르

    public Music(String genre, int played, int id) {
      this.genre = genre;
      this.played = played;
      this.id = id;
    }

    // 정렬 기준: 재생 횟수 내림차순, 같으면 id 오름차순
    @Override
    public int compareTo(Music other) {
      if (this.played == other.played) return this.id - other.id;
      return other.played - this.played;
    }

    public String getGenre() { return genre; }
  }

  public int[] solution(String[] genres, int[] plays) {
    return IntStream.range(0, genres.length)
        // index를 기반으로 Music 객체 생성
        .mapToObj(i -> new Music(genres[i], plays[i], i))
        // 장르별로 그룹화: Map<String, List<Music>> 형태
        .collect(Collectors.groupingBy(Music::getGenre))
        // entrySet()으로 Map을 순회하며 Stream 생성
        .entrySet().stream()
        // 장르별 총 재생 수 기준으로 정렬 (내림차순) (1번 기준) 
        .sorted((a, b) -> sum(b.getValue()) - sum(a.getValue()))
        // 각 장르별로 곡 정렬 후 최대 2곡까지 선택 (2, 3번 기준 - 최대 2개)
        .flatMap(e -> e.getValue().stream().sorted().limit(2))
        // Music 객체에서 id만 추출
        .mapToInt(m -> m.id)
        // 결과 배열 반환
        .toArray();
  }

  // 주어진 음악 리스트의 총 재생 수 계산
  private int sum(List<Music> list) {
    return list.stream().mapToInt(m -> m.played).sum();
  }
}