문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
아이디어
고려해야할 부분이 많은 문제인 것 같다. 먼저 살펴보자면 정렬 첫번째는 장르별 가장 많이 재생된 장르부터 나열한다. 그다음은 장르 내에서 많이 재생된 노래를 2개씩(or 1개) 수록한다. 다행히 모든 장르의 재생된 횟수는 다르므로 장르가 같아질 때의 우선순위는 고려를 하지 않아도 된다.
예시를 한번 보자.
| genres | plays | return |
| ["classic", "pop", "classic", "classic", "pop"] | [500, 600, 150, 800, 2500] | [4, 1, 3, 0] |
장르는 classic과 pop 두 종류가 있고 각각의 총 합은 classic = 1450, pop = 3100 이다. 따라서 가장 먼저 수록되어야할 장르는 pop인 고유 번호(index) 4와 1이 먼저 수록되어야 한다. 둘 중 index 4(2500회)가 index 1(600회) 보다 크므로 4가 먼저 수록되고 그다음 1이 수록된다.
그다음 장르가 classic 인 노래가 수록되는데 재생 횟수가 index3(800회), index1(600회), index2(150회)이며 베스트앨범은 장르별 가장 많이 재생된 노래 2곡을 수록하기 때문에 index3(800회)과 index1(600회)가 수록된다.
코드구현(자바)
먼저 장르별 재생 횟수가 많은 순으로 내림차순으로 장르를 정렬해주어야 한다. 이는 Hash-위장(프로그래머스) 에서 사용한 Map의 getOrDefault 로직과 Collection의 sort 를 이용해 내림차순으로 정렬해줄 수 있다.
Map <String, Integer> genresList = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
genresList.put(genres[i], genresList.getOrDefault(genres[i],0) + plays[i]);
}
List<String> onlyGenres = new ArrayList<>(genresList.keySet());
Collections.sort(onlyGenres, (p1, p2) -> genresList.get(p2) - genresList.get(p1));먼저 genresList 에 장르(key값)에 재생횟수(value값)를 누적해서 더하여 저장해줬다. 그리고 genresList 의 key 값만 담은 ArrayList인onlyGenres 를 만들어 Collections 를 사용해 onlyGenres 를 genresList의 value 값(누적된 재생횟수) 기준으로 내림차순 정렬해주었다.
그리고 genre와 play, 그리고 index 까지 비교해야하므로 여러 변수를 담을 수 있는 별도의 클래스를 만들어주었다.
static class Play{
String genre;
int play;
int idx;
public Play(String genre, int play, int idx) {
this.genre = genre;
this.play = play;
this.idx = idx;
}최종적으로 수록된 곡을 담기 위한 ArrayList 도 선언해준다.
// 수록된 곡을 담기 위한 ArrayList
ArrayList<Play> addList = new ArrayList<>();이제 이중 for문을 돌려 제일 바깥은 onlyGenres의 size 만큼, 안쪽 for 문은 plays의 length 만큼 돌려준다.
for (int i = 0; i < onlyGenres.size(); i++) {장르를 담을 수 있는 gen이라는 String 변수와 장르에 대한 Play 클래스를 담을 수 있는 playList라는 ArrayList를 선언해주었다.
만약에 gen.equals(genres[j])일 경우 Play 클래스에 장르, 재생횟수, 인덱스 값으로 선언하여 playList에 add해주었다.
// cnt(add한 횟수)가 2를 넘으면 브레이크!
int cnt = 0;
String gen = onlyGenres.get(i);
ArrayList<Play> playList = new ArrayList<>();
for (int j = 0; j < plays.length; j++) {
if (gen.equals(genres[j])) {
playList.add(new Play(gen, plays[j], j));
}
}장르만의 playList가 만들어졌다.
이제 Collections.sort를 사용해 playList를 재생횟수 기준으로 내림차순으로 정렬해준다. 정렬 후 playList.size() 만큼 for문을 돌려 cnt(add한 횟수)가 2가 넘지 않을 때까지 addList(최종 수록된 곡을 담는 ArrayList)에 add해준다.
// for 문 다 돌았을 때 장르 하나의 리스트가 완성됨 해당 클래스 리스트를 플레이 횟수 기준으로 내림차순 정렬해준다.
Collections.sort(playList, (p1, p2) -> p2.play - p1.play);
for (int m = 0; m < playList.size(); m++) {
if(cnt != 2) {
addList.add(playList.get(m));
cnt++;
} else break;
}
}마지막으로 answer 를 addList.size의 공간으로 선언해서 for문을 돌려 클래스에 담겨있는 idx를 담아주고 return 하면 끝!
int[] answer = new int[addList.size()];
for (int i = 0; i < addList.size() ; i++) {
answer[i] = addList.get(i).idx;
}
return answer;전체코드
import java.util.*;
public class Solution {
static class Play{
String genre;
int play;
int idx;
public Play(String genre, int play, int idx) {
this.genre = genre;
this.play = play;
this.idx = idx;
}
}
public int[] solution(String[] genres, int[] plays) {
Map <String, Integer> genresList = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
genresList.put(genres[i], genresList.getOrDefault(genres[i],0) + plays[i]);
}
List<String> onlyGenres = new ArrayList<>(genresList.keySet());
Collections.sort(onlyGenres, (p1, p2) -> genresList.get(p2) - genresList.get(p1));
// 수록된 곡을 담기 위한 ArrayList
ArrayList<Play> addList = new ArrayList<>();
for (int i = 0; i < onlyGenres.size(); i++) {
// cnt(add한 횟수)가 2를 넘으면 브레이크!
int cnt = 0;
String gen = onlyGenres.get(i);
ArrayList<Play> playList = new ArrayList<>();
for (int j = 0; j < plays.length; j++) {
if (gen.equals(genres[j])) {
playList.add(new Play(gen, plays[j], j));
}
}
System.out.println();
// for 문 다 돌았을 때 장르 하나의 리스트가 완성됨 해당 클래스 리스트를 플레이 횟수 기준으로 내림차순 정렬해준다.
Collections.sort(playList, (p1, p2) -> p2.play - p1.play);
for (int m = 0; m < playList.size(); m++) {
if(cnt != 2) {
addList.add(playList.get(m));
cnt++;
} else break;
}
}
int[] answer = new int[addList.size()];
for (int i = 0; i < addList.size() ; i++) {
answer[i] = addList.get(i).idx;
}
return answer;
}
}
댓글