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

문제 설명

스트리밍 서비스에서 장르별로 가장 많이 재생된 노래를 모아 베스트 앨범을 제작하려고 합니다.
각 노래는 고유 번호를 가지며, 다음 기준에 따라 노래를 선정해야 합니다:

1. 장르별 총 재생 수가 높은 순서로 장르를 선정합니다.
2. 각 장르 내에서 재생 수가 많은 순서로 최대 두 곡까지 선택합니다.
3. 재생 수가 동일할 경우, 고유 번호가 낮은 노래를 우선 선택합니다.

장르별로 가장 인기 있는 곡들을 추려내는 것이 핵심입니다.

---

제한 사항

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

---

해결 방법

알고리즘: 정렬, 해시맵

1. 장르별 총 재생 수를 구해 맵에 저장합니다.
2. 장르별로 각 노래의 [재생 수, 고유 번호]를 모아 저장합니다.
3. 장르별 총 재생 수가 높은 순으로 정렬합니다.
4. 각 장르에서 재생 수가 높은 순으로 정렬하되, 같은 재생 수일 경우 고유 번호가 낮은 순으로 정렬합니다.
5. 각 장르에서 최대 두 곡까지 고유 번호를 선택하여 결과에 추가합니다.

---

시간 복잡도

• 장르 및 노래 정리에 O(N)
• 정렬에 O(G log G + N log N) (G: 장르 수, N: 노래 수)
• 전체적으로 O(N log N)

---

구현 코드

function solution(genres, plays) {
  const genreMap = new Map();
  const songMap = new Map();
  const n = genres.length;

  for (let i = 0; i < n; i++) {
    const genre = genres[i];
    const play = plays[i];

    genreMap.set(genre, (genreMap.get(genre) || 0) + play);

    if (!songMap.has(genre)) songMap.set(genre, []);
    songMap.get(genre).push([play, i]);
  }

  const sortedGenres = Array.from(genreMap).sort((a, b) => b[1] - a[1]);

  const answer = [];

  for (const [genre] of sortedGenres) {
    const songs = songMap.get(genre);

    songs.sort((a, b) => b[0] - a[0] || a[1] - b[1]);

    for (let i = 0; i < Math.min(2, songs.length); i++) {
      answer.push(songs[i][1]);
    }
  }

  return answer;
}