[programmers] 베스트앨범

문제 : https://programmers.co.kr/learn/courses/30/lessons/42579#

---

수록 기준

1. 속한 노래가 많이 재생된 장르를 먼저 수록.

2. 장르 내에서 많이 재생된 노래를 먼저 수록.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록

 

---

map를 이용했다.

사용한 map은 총 3가지.

1. key: 장르 / value : 재생수, 고유번호를 원소로 가지는 배열 => songMap

2. key: 장르 / value : 해당장르의 총 재생수 => cntMap

3. key: 해당장르의 총 재생수 / value: 장르 [cntMap의 key, value를 바꾼 map] => rcntMap

 

1번 songMap은 수록 기준 2, 3을 만족하기 위해서 사용하고

3번 rcntMap은 수록 기준 1을 만족하기 위해서 사용했다.

2번 cntMap은 수록 기준 3번 rcntMap을 만들기 위해 사용했다.

 

입력 값으로 songMap, cntMap을 채운 뒤 cntMap으로 rcntMap을 만든다.

 

rcntMap을 역순으로 탐색한다.

역순으로 탐색한 이유는 c++의 map은 key 순으로 오름차순하는 것이 디폴트 값이다. (map 생성시 3번째 파라미터로 greater<자료형>을 추가하면 내림차순으로 만들수도 있긴하다.)

그런데 1번 수록 기준은 속한 노래가 많이 재생된 장르가 우선이므로 key 값인 총 재생수가 큰 것부터 탐색해야 한다.

 

rcntMap의 value로 장르를 가져올 수 있다. 이 장르를 key값으로 하는 songMap의 value를 가져온다.

가져온 value는 <재생수, 고유번호>를 가지는 배열이다. 

이를 조건에 맞게 정렬한다.

이 때 봐야 할 조건은 2, 3이다.

조건 2에 의해 재생 수가 큰 순으로 정렬되어야 하고 만약 재생 수가 같은 노래가 있다면 조건 3에 의해 고유 번호가 낮은 순으로 정렬한다.

배열 정렬이 끝났으면 앞에서부터 1개 혹은 최대 2개의 고유번호를 정답 배열에 차례대로 넣는다.

이를 rcntMap의 탐색이 끝날때까지 반복한다.

 

N = 노래 수.

시간복잡도는 O(NlogN..?)

공간복잡도는 O(N). 

---

소스코드 : https://gist.github.com/fpdjsns/9deaf930655503dcb663919caa3c77f2