[프로그래머스] 베스트앨범 - JAVA

베스트앨범

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres	plays	return
[classic, pop, classic, classic, pop]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

풀이

HashMap과 List를 이용해서 풀었습니다.

 

먼저 Map에 key , value형태로 들어가는데

key에는 장르값 value에는 play횟수가 들어갑니다

 

xxxxxxxxxx
HashMap<String,Integer>map = new HashMap<>();
​
for(int i=0; i<genres.length; i++) {
    if(map.containsKey(genres[i])){
        map.put(genres[i],map.get(genres[i])+plays[i]);
    }
    else {
        map.put(genres[i],plays[i]);
    }
}

map에 이미 key값이 있을경우 play횟수를 더해줘야하니

map.get("key값") + plays[i]를 통해 누적을 시켜줍니다.

 

map에서 put은 중복된 key값이 있으면 덮어쓰는 형식입니다.

예를들어 map("classic", 2)가 이미 존재 할 때

map.put("classic", 1)을 put해주면 key = classic, value = 1 로 덮어써지는데 덮어쓰는것을 원하지 않고 누적을 해줘야하니

기존의 map의 value값을 map.get(key)를 통해서 얻어와서 누적시켜주는 형태입니다.

 

 

그 다음 플레이 횟수가 많은 순서대로 장르들을 정렬시켜야 하는데 이 떄 map은 따로 정렬이 없으니 list를 이용해서 정렬해줍니다.

 

xxxxxxxxxx
ArrayList<String>list = new ArrayList<>(map.keySet());
​
Collections.sort(list, new Comparator<String>() {
​
@Override
public int compare(String o1, String o2) {
return map.get(o2).compareTo(map.get(o1));
}
});

 

list의 생성자에 map.keySet()을 통해 map에 들어있는 key값만 가져옵니다 (문제의 예제에서 "classic" "pop")

 

그다음 key값을 얻어왔으니 리스트에 map을 정렬해준 값을 넣어줍니다.

 

 

전체코드

x
import java.util.*;
class Solution {
    public static int[] solution(String[] genres, int[] plays) {
       
        
        HashMap<String,Integer>map = new HashMap<>();
        
        for(int i=0; i<genres.length; i++) {
            if(map.containsKey(genres[i])){
                map.put(genres[i],map.get(genres[i])+plays[i]);
            }
            else {
                map.put(genres[i],plays[i]);
            }
        }
        ArrayList<String>list = new ArrayList<>(map.keySet());
        ArrayList<Integer>ans = new ArrayList<>();
        Collections.sort(list, new Comparator<String>() {
​
            @Override
            public int compare(String o1, String o2) {
                return map.get(o2)-map.get(o1);
            }
        });
        int idx = 0;
        ArrayList<Node>tmp = new ArrayList<>();
        for(String key : list) {
            tmp.clear();
            for(int i=0; i<plays.length; i++) {
                if(genres[i].equals(key)) {
   
                    tmp.add(new Node(i,plays[i]));
                }
            }
            
            Collections.sort(tmp);
            
            if(tmp.size()==1) {
                ans.add(tmp.get(0).origin_num);
            }
            else {
                for(int j=0; j<2; j++) {
                    ans.add(tmp.get(j).origin_num);
                }
            }
            
            
        }
        int answer[] = new int[ans.size()];
        for(int a : ans) {
            answer[idx++] = a;
        }
        return answer;
    }
}
class Node implements Comparable<Node>{
    int origin_num,play_cnt;
    Node(int origin_num, int play_cnt){
        this.origin_num = origin_num;
        this.play_cnt = play_cnt;
    }
    @Override
    public int compareTo(Node o) {
        if(this.play_cnt == o.play_cnt) {
            return this.origin_num - o.origin_num;
        }
        return o.play_cnt- this.play_cnt;
    }
}