42579. 베스트앨범

프로그래머스 42579번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 베스트앨범 | 프로그래머스 스쿨

풀이

아이디어

정렬 기준이 두 단계로 나뉘어져 있었기 때문에 우선 장르별로 노래를 그룹화한 뒤에 장르 정렬 → 장르 내 노래 정렬 순서로 처리했다.

1단계: 장르별 노래 그룹화

Map을 이용해서 장르를 key로, 해당 장르에 속한 노래들의 고유번호(인덱스)배열을 value로 저장했다. 인덱스가 곧 고유번호 역할을 하기 때문에 별도로 노래 정보를 저장할 필요는 없었다.

  const genresMap = new Map();
  genres.forEach((genre, id) => {
    if (genresMap.has(genre)) {
      genresMap.set(genre, [...genresMap.get(genre), id]);
    } else {
      genresMap.set(genre, [id]);
    }
  });

2단계: 장르 정렬

장르별 총 재생 횟수를 기준으로 내림차순 정렬했다. 각 장르의 노래 배열을 순회하면서 plays에서 재생 횟수를 가져와 합산해서 비교했다.

  const sortedGenres = [...genresMap.values()].sort((aSongs, bSongs) => {
    const aPlays = aSongs.reduce((acc, cur) => acc + plays[cur], 0);
    const bPlays = bSongs.reduce((acc, cur) => acc + plays[cur], 0);
    return bPlays - aPlays;
  });

3단계: 장르 내 노래 정렬과 상위 2개 선택

각 장르 내에서 재생 횟수가 높은 순으로, 같다면 고유번호가 낮은 순으로 정렬한 뒤에 상위 2개만 선택했다.

  const answer = [];
  sortedGenres.forEach((songs) => {
    const sortedSongs = songs
      .sort((a, b) => {
        if (plays[a] === plays[b]) return a - b;
        return plays[b] - plays[a];
      })
      .slice(0, 2);
    answer.push(...sortedSongs);
  });

시간 복잡도

N이 노래 수, G가 장르 수일 때

• 장르별로 그룹화하는데 O(N)
• 장르 정렬 : 장르별로 정렬하는데에는 O(GlogG), 각 장르별 노래를 재생횟수를 더하는데에 총 O(N)
• 장르 내 노래 정렬 : O(N)

N이 훨씬 크므로… 전체 시간 복잡도는 O(NlogN)이다.