문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
문제 이해
첫 번째로 가장 많이 재생된 장르의 인덱스를 추가하고
두 번째론 장르 내에서 많이 재생된 노래를 추가한다.
이때 재생 횟수가 같으면 고유 번호가 낮은 노래의 인덱스를 먼저 추가한다.
장르가 ["classic", "pop", "classic", "classic", "pop"] ,
재생 횟수가 [500, 600, 150, 800, 2500] 일 때
classic은 1,450회 재생(0: 500, 2: 150, 3: 800), pop은 3,100회 재생(1: 600, 4: 2,500)
따라서 pop이 더 많이 재생되었고, 그 중 4번 인덱스가 더 많이 재생되었기 때문에 [4, 1] 추가
classic에서는 3번, 0번, 2번 순으로 많이 재생되었고, 두 개씩만 모아 베스트 앨범을 출시한다는 조건이 있기 때문에
[3, 0] 추가
최종 return은 [4, 1, 3, 0]이 되어야 한다.
처음 든 생각은 장르와 재생 횟수를 HashMap을 사용해서 각각 key와 value 로 저장하면 되겠다
라고 생각을 했는데 장르가 중복돼서 못 하겠다 ,, 했는데 ? 모든 장르는 재생된 횟수가 다르단다.
그럼 재생 횟수를 key로, 장르를 value로 잡고 해시맵을 사용해서 풀면 될 것 같다.
→ 모든 장르는 재생된 횟수가 다릅니다. 라는 건 음악별로 재생된 수가 다르다는 게 아니라 장르별로 다 다르다는 거였다 ,,
장르와 재생 횟수를 해시맵으로 관리하되, 장르별 총 재생 횟수를 저장해서 어떤 장르가 가장 많이 재생됐는지를 확인하고
각 장르별로 가장 많이 재생된 두 개를 뽑아서 그 인덱스를 배열에 추가해주면 될 거 같다.
장르별 총 재생 횟수를 해시맵에 저장하고, 재생 횟수가 가장 많은 장르(key)를 가져와서
그 장르 내에서 첫 번째와 두 번째로 많이 재생된 인덱스를 가져오려고 했는데 가져올 방법이 생각나질 않았다.
특정 키값와 장르 배열을 비교해서 둘이 같을 경우 인덱스를 저장하고, 그 인덱스에 있는 재생 횟수의 크기를 비교하려고 했는데 방법이 도저히 생각나질 않았다 ,,
차라리 해시맵을 하나 더 만들어서 key로는 장르, value로는 장르별 재생 횟수를 저장하면 ?
그렇게 해서 장르별 재생 횟수를 계속 추가해주면 되지 않을까 싶어서 구현해보려고 한다.
1차 코드
package programmers.P42579;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Main {
public static void main(String[] args) {
String[] g = {"classic", "pop", "classic", "classic", "pop"};
int[] p = {500, 600, 150, 800, 2500};
System.out.println(Arrays.toString(solution(g, p)));
}
public static int[] solution(String[] genres, int[] plays) {
HashMap<String, Integer> hm = new HashMap<>();
HashMap<String, List<int[]>> songs = new HashMap<>();
int n = genres.length;
for (int i = 0; i < n; i++) {
hm.put(genres[i], hm.getOrDefault(genres[i], 0) + plays[i]);
if (!songs.containsKey(genres[i])) {
songs.put(genres[i], new ArrayList<>());
}
songs.get(genres[i]).add(new int[]{i, plays[i]});
}
ArrayList<String> keys = new ArrayList<>(hm.keySet());
keys.sort((a, b) -> hm.get(b) - hm.get(a));
ArrayList<Integer> list = new ArrayList<>();
for (String key : keys) {
List<int[]> genre = songs.get(key);
genre.sort((a, b) -> {
if (b[1] - a[1] == 0) {
return Integer.compare(a[0], b[0]);
}
return Integer.compare(b[1], a[1]);
});
int i = 0;
for (int[] song : genre) {
if (genre.size() < 2) {
list.add(song[0]);
break;
}
if (i == 2) {
break;
}
list.add(song[0]);
i++;
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
생각난대로 작성한 코드라 지저분하기도 하고, 불필요한 코드가 많아서 리팩토링하겠다.
2차 코드
package programmers.P42579;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Main {
public static void main(String[] args) {
String[] g = {"classic", "pop", "classic", "classic", "pop"};
int[] p = {500, 600, 150, 800, 2500};
System.out.println(Arrays.toString(solution(g, p)));
}
public static int[] solution(String[] genres, int[] plays) {
HashMap<String, Integer> hm = new HashMap<>();
HashMap<String, List<int[]>> songs = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
hm.put(genres[i], hm.getOrDefault(genres[i], 0) + plays[i]);
songs.computeIfAbsent(
genres[i], k -> new ArrayList<>())
.add(new int[]{i, plays[i]}
);
}
ArrayList<String> keys = new ArrayList<>(hm.keySet());
keys.sort((a, b) -> Integer.compare(hm.get(b), hm.get(a)));
ArrayList<Integer> list = new ArrayList<>();
for (String key : keys) {
List<int[]> genre = songs.get(key);
genre.sort((a, b) -> {
if (b[1] == a[1]) {
return Integer.compare(a[0], b[0]);
}
return Integer.compare(b[1], a[1]);
});
for (int i = 0; i < Math.min(2, genre.size()); i++) {
list.add(genre.get(i)[0]);
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
songs에 장르별 재생 횟수를 넣을 때 if문을 사용하지 않고 computeIfAbsent메서드를 사용해 코드를 간결화했고,
코드의 의도를 나타내기 위해 hm.get(b) - hm.get(a) 대신 Integer.compare(hm.get(b), hm.get(a)) 를 사용했다.
마찬가지로 b[1] - a[1] == 0 대신 b[1] == a[1] 사용했고
장르별로 두 개만 선택해서 리스트에 넣는 코드를 간결하게 리팩토링했다.
막상 풀어보니 그렇게 어려운 문제는 아니었는데, 아이디어를 생각하기가 좀 어려웠다.
해시맵에 대한 고민을 많이 할 수 있는 시간이라 좋았다.