풀이 파트에 각 코드에 대한 설명을 주석으로 자세하게 다루었으니 참고하시면 좋습니다.
문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
관찰
정렬을 해야 될 것 같은 느낌이 든다.
- genres 순 내림차순
- plays 순 내림차순
- 고유 번호(genres[i])
- plays 순 내림차순
우리가 저장해야 되는 정보가 무엇일까?
- 장르에 따른 총 재생된 횟수
Map<String, Integer>필요
- 각 장르에 속하는 곡들의 고유 번호
Map<String, List<Integer>>필요
알고리즘
대단한 알고리즘이 필요하지 않다.
최적화의 과정을 물어보는 문제도 아닌데다가,그냥 주어진 입력에 대해서, 어떤 값을 저장하면 좋을지와 이를 어떻게 활용하면 될지 적절한 자료구조를 정하여 데이터를 저장하면 된다.
포인트
- 역순 정렬은 어떻게 하면 될지
- 람다식을 이용한 정렬
- Map과 관련된 몇가지 메서드들
풀이
주석 없는 풀이와 주석 달린 코드 두개를 준비했습니다.
주석 없는 풀이
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, Integer> genrePlays = new TreeMap<>();
Map<String, List<Integer>> genreSongs = new TreeMap<>();
for (int i = 0; i < genres.length; i++) {
String genre = genres[i];
int play = plays[i];
genrePlays.merge(genre, play, Integer::sum);
genreSongs.computeIfAbsent(genre, k -> new ArrayList<>()).add(i);
}
List<String> genreList = new ArrayList<>(genrePlays.keySet());
genreList.sort((o1, o2) -> genrePlays.get(o2) - genrePlays.get(o1));
List<Integer> answer = new ArrayList<>();
for (String genre : genreList) {
List<Integer> songs = genreSongs.get(genre);
songs.sort((o1, o2) -> {
if (plays[o1] == plays[o2]) {
return o1 - o2;
}
return plays[o2] - plays[o1];
});
songs.stream().limit(2).forEach(answer::add);
}
return answer.stream().mapToInt(i -> i).toArray();
}
}
주석 있는 풀이
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, Integer> genrePlays = new TreeMap<>();
Map<String, List<Integer>> genreSongs = new TreeMap<>();
// 입력된 String 배열로 부터 장르와 고유 번호를, int 배열로 부터 재생된 횟수를 추출할 수 있다.
for (int i = 0; i < genres.length; i++) {
String genre = genres[i];
int play = plays[i];
// 장르별 총 재생 수를 구하는 과정
// merge 메서드를 이용하여 getOrDefault 메서드를 대체 할 수 있다.
genrePlays.merge(genre, play, Integer::sum);
// genrePlays.put(genre, genrePlays.getOrDefault(genre, 0) + play);
// 장르와 고유 번호를 저장한다.
// computeIfAbsent 메서드를 이용하여 if 분기를 제거할 수 있다.
genreSongs.computeIfAbsent(genre, k -> new ArrayList<>()).add(i);
// if (!genreSongs.containsKey(genre)) {
// genreSongs.put(genre, new ArrayList<>());
// }
// genreSongs.get(genre).add(i);
}
// 재생된 횟수가 많은 장르를 담기 위한 리스트
List<String> genreList = new ArrayList<>(genrePlays.keySet());
// 장르 리스트를 정렬하는 2가지 방법이 있다.
// 속도 차이는 별로 없다.
// 1-1. sort 메서드 내부 Comparator 구현 (람다식)
genreList.sort((o1, o2) -> genrePlays.get(o2) - genrePlays.get(o1));
// 1-2. sort 메서드 내부 Comparator 구현 (comparingInt)
// genreList.sort(Comparator.comparingInt(genrePlays::get).reversed());
// 2. Collections.sort 메서드 사용
// Collections.sort(genreList, (o1, o2) -> genrePlays.get(o2) - genrePlays.get(o1));
// 노래의 고유 번호를 저장하기 위한 정답 리스트
List<Integer> answer = new ArrayList<>();
for (String genre : genreList) {
List<Integer> songs = genreSongs.get(genre);
// 문제 설명 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
// 조건을 만족시키기 위하여 해당 장르에 속한 노래들을 정렬할 때,
// 같은 재생 횟수를 가진 노래들은 고유 번호가 낮은 노래가 먼저 오도록 정렬한다.
songs.sort((o1, o2) -> {
if (plays[o1] == plays[o2]) {
return o1 - o2;
}
return plays[o2] - plays[o1];
});
// 문제 설명 첫줄,
// 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다.
// 제한 사항 5번째 줄,
// 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
// 이 조건을 만족시키기 위하여 아래와 limit 메서드를 이용하여 작성합니다.
songs.stream().limit(2).forEach(answer::add);
}
return answer.stream().mapToInt(i -> i).toArray();
}
}