<Demopeu/>

[프로그래머스] 42579 배스트앨범 JavaScript

[프로그래머스] 42579 배스트앨범 JavaScript

problem-solving프로그래머스정렬Map

📌 문제 설명

베스트 앨범 문제 보기

📌 문제 접근

주어진 두 배열을 다루기 쉬운 하나의 데이터 구조로 정규화 하는 것이 핵심인 문제. 배열 메서드를 체이닝 하여 하나의 데이터파이프처럼 작성하였다.

다만, 빠르게 접근하고 풀다보니 가독성이 약간 떨어진다.

📌 내가 작성한 코드

function solution(genres, plays) {
  return [
    ...genres.reduce((genres_map, genre, number) => {
      const play = plays[number];

      const genre_play = genres_map.get(genre)
        ? genres_map.get(genre)
        : [[], 0];

      genre_play[0].push([number, play]);

      genres_map.set(genre, [genre_play[0], genre_play[1] + play]);

      return genres_map;
    }, new Map()),
  ]
    .sort((a, b) => b[1][1] - a[1][1])
    .flatMap((e) => {
      return e[1][0]
        .sort((a, b) => {
          if (a[1] === b[1]) return a[0] - b[0];

          return b[1] - a[1];
        })
        .slice(0, 2)
        .flatMap((e) => e[0]);
    });
}

📌 시간 복잡도

  • 장르별로 곡을 분류하는 reduce: O(N)
  • 장르를 재생 횟수로 정렬: O(G log G) (G는 장르 수)
  • 각 장르 내 곡을 정렬하고 상위 2개 선택: O(N log N)
  • 전체 시간 복잡도: O(N log N)

📌 참고 링크