[Lv3] 베스트 앨범

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

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

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]번 노래를 그다음에 수록합니다.

 

 

---

 

1. 장르 총 재생량 우선

2. 그 장르 내에 재생량 순서로 최대 2개씩

 

답에 넣을 정보: index

추가 필요 정보: 곡별 재생수, 장르별 총 재생수

확정지을 수 없는(문제마다 변하는) 정보: 장르 종류 갯수

 

 

입출력 예를 보면 알 수 있듯이, index(순서값)를 확인할 수 있어야 함.

 

장르가 몇 개나 나올지 알 수가 없다.. Map<장르명, ArrayList<int[] {i, plays[i]}>>로 하고,

ArrayList<ArrayList<int[]>>에 list들을 몰아박고, list 안의 list의 plays를 총합해서 역순정렬..??

코드는 짜겠지만, 나중에 보면 다시 보기 힘들듯;;

 

여기선 Genre 클래스를 만들어 여기에 장르명, total을 저장해두고, 각 곡별 [index, play]가 담긴 que를 넣어둘겁니다.

그리고 ArrayList<Genre>를 쓸겁니다.

Comparator<int[]> cmp_arr = (a,b)->{
    if(a[1]!=b[1]) return b[1]-a[1];
    else return a[0]-b[0];
};

class Genre {
    String name;
    int total;
    PriorityQueue<int[]> songs;
    public Genre(String name, int index, int play) {
        this.name = name;
        this.total = play;
        this.songs = new PriorityQueue<>(cmp_arr);
        this.songs.add(new int[] {index, play});
    }
}

songs라는 우선순위 큐는 곡의 play가 높을 수록, play가 같다면 index가 낮을 수록 우선하게 만듭니다.

 

 

ArrayList<Genre> list = new ArrayList<>();
for(int i=0;i<genres.length;i++) {
    if(list.isEmpty()) list.add(new Genre(genres[i], i, plays[i]));
    else {
        boolean isExist = false;
        for(Genre g:list) {
            if(g.name.equals(genres[i])) {
                g.total+=plays[i];
                g.songs.add(new int[] {i, plays[i]});
                isExist = true;
                break;
            }
        }
        if(!isExist) list.add(new Genre(genres[i], i, plays[i]));
    }
}

ArrayList<Genre>를 두고, String[] genres를 돌면서,

새 장르가 등장하면 장르명과 i, 현재곡재생수를 토대로 새 장르를 생성해서 넣어줍니다.

이미 장르가 있다면 장르의 total을 올려주고, 곡에 대한 정보를 해당 songs에 넣어줍니다.

 

Comparator<Genre> cmp_l = (a,b)->{
    return b.total-a.total;
};
Collections.sort(list, cmp_l);

list를 안의 Genre들의 total에 내림차순으로 정렬합니다.

 

PriorityQueue나 TreeMap을 사용하지 못한 것은, 얘들은 집어넣어질 때만 그 정보를 바탕으로 정렬합니다.

즉, 이미 넣어진 Genre의 total에 변화를 줘도 새로 정렬하진 않습니다.

어차피 정렬은 모든 정보가 기입된 후에 한 번만 해도 되니, List를 사용했습니다.

 

 

int amount = 0;
for(Genre g:list) {
    amount++;
    if(g.songs.size()>1) amount++;
}
int[] answer = new int[amount];

list에 든 Genre 수 만큼 기본적으로 1곡은 있을테고, 최대 2곡 수록이니 songs가 1보다 크면 하나 자리 더 마련합니다.

 

 

int index=0;
while(index<answer.length) {
    Genre g = list.remove(0);
    answer[index++] = g.songs.poll()[0];
    if(!g.songs.isEmpty()) answer[index++] = g.songs.poll()[0];
}
return answer;

list에서 0번째를 꺼내면서(total이 큰 순임. 문제에서 total은 항상 다르게 주어진다고 명시되어있음.)

그 songs 중 첫번째를 꺼내주고,

두번째가 있다면 한 번 더 꺼내줌.

 

이렇게 배열 완성해서 반환.