문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
입출력 예
🥕나의 풀이
1. 우선 이 문제를 풀기 위해 각 앨범의 고유번호(index)와 재생횟수(plays)를 필드로 하는 Music객체를 생성하였다.
2. 그 후, 음악의 장르를 Key로하고 각 장르에 해당하는 하나 이상의 노래들의 정보를 담은 Music 클래스를 List에 담아 Value로 하는 map을 만들었다.
3. 2번에서 선언한 map 이외에 각 장르에 해당하는 노래의 전체 재생 횟수를 Value로하는 map을 하나 더 만들어서, 내림차순으로 정렬하였다.
4. 3번에서 정의한 map의 key 는 재생횟수가 많은 장르 순으로 정렬되어 있으므로 순서대로 탐색하여, 2번에서 정의한 Map의 Value값을 참조한다면 답을 찾을 수 있을 것이라고 생각했다.
5. 2번에서 정의한 Map의 Value는 재생 횟수와 고유번호에 관계없이 무작위로 나열되어 있는데, 이것에 대한 정렬이 필요했다. 정렬 기준은 Music객체의 plays이며, 만약 plays가 같다면 index가 작은 순서대로 정렬하면된다. (방법은 Music 클래스 선언 부분에 나와있으니 코드를 참고하시길...)
import java.util.*;
class Music implements Comparable<Music>{
int index = 0;
int plays = 0;
Music(int idx, int play){
index = idx;
plays = play;
}
@Override
public int compareTo(Music music) {
if (music.plays < plays) { //오름차순 정렬일 때 부등호의 방향임. 현재 reverseOrder()하였으므로 내림차순으로 plays가 정렬될거임.
return 1;
}
else if (music.plays > plays) {
return -1;
}
else if(music.plays==plays){
if(music.index > index){ //원래는 부등호의 방향이 반대여야 하지만, index는 reverseOrder()해도 오름차순으로 나와야 하므로 이와 같이 함!
return 1;
}
else if(music.index < index){
return -1;
}
}
return 0;
}
}
class Solution {
ArrayList<Music> list = new ArrayList<>();
Map <String, ArrayList<Music>> map = new LinkedHashMap<>();//맵 안에 ArrayList안에 Music객체 선언.
Map<String, Integer> number = new HashMap<>();
List<Integer> result = new ArrayList<>();
public int[] solution(String[] genres, int[] plays) {
int[] answer = {};
for(int i=0;i<genres.length;i++){
if (!map.containsKey(genres[i])) { //맵의 Value값을 List로 먼저 초기화 해준다.
map.put(genres[i], new ArrayList<>());
}
map.get(genres[i]).add(new Music(i, plays[i]));//초기화 후, get()으로 Value를 불러와서 그 안에다가 객체를 생성한 것을 add한다.
}
//재생 횟수의 합을 저장해놓은 map을 하나 더 만든다. map이름 : number
for(int i=0;i<genres.length;i++){
if(!number.containsKey(genres[i])){
number.put(genres[i], plays[i]);
}
else{
number.put(genres[i], number.get(genres[i]) + plays[i]);
}
}
//number 맵을 Value값의 내림차순으로 정렬한다.
ArrayList<Map.Entry<String, Integer>> temp = new ArrayList <>(number.entrySet());
temp.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1,
Map.Entry<String, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
// //temp가 내림차순으로 잘 정렬됐는지 확인하기.
for(int i=0;i<temp.size();i++){
System.out.printf("%s %d\n", temp.get(i).getKey(), temp.get(i).getValue());
}
//map에 들어있는 key별 value의 List를 getmusic List에 옮겨 담았다.
// getmusic 중에서 play수가 높은 것 부터 정렬하여 도출하는 것이 중요.
for(int i=0;i<temp.size();i++){
String best = temp.get(i).getKey();
ArrayList<Music> getmusic = new ArrayList <>();
getmusic.addAll(map.get(best));
Collections.sort(getmusic, Collections.reverseOrder());
if(getmusic.size()>=2){
for(int j=0;j<2;j++){
result.add(getmusic.get(j).index);
}
}
else if(getmusic.size()==1){
result.add(getmusic.get(0).index);
}
}
answer = new int[result.size()];
for(int i=0;i<result.size();i++){
answer[i]=result.get(i);
}
return answer;
}
}