## 🌟 문제
[코딩테스트 연습 - 베스트앨범 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/42579)
장르별로 가장 많이 재생된 노래를 최대 두개씩 모아서 베스트 앨범을 만드는 문제.
수록 기준
1. 속한 노래의 재생 횟수 합이 가장 많은 장르를 먼저 수록
2. 장르 내에서 많이 재생된 노래를 먼저 수록
3. 재생 횟수가 같으면 고유 번호가 낮은 노래를 먼저 수록
## 🌟 풀이
정렬 기준이 두 단계로 나뉘어져 있었기 때문에 우선 장르별로 노래를 그룹화한 뒤에 장르 정렬 → 장르 내 노래 정렬 순서로 처리했다.
### 1단계: 장르별 노래 그룹화
우선 Map을 이용해서 장르를 key로, 해당 장르에 속한 노래들의 고유번호(인덱스)배열을 value로 저장했다. 인덱스가 곧 고유번호 역할을 하기 때문에 별도로 노래 정보를 저장할 필요는 없었다.
```javascript
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에서 재생 횟수를 가져와 합산해서 비교했다.
```javascript
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개만 선택했다.
```javascript
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)이다.