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

프로그래머스, 베스트앨범 문제 링크

베스트앨범을 만드는 조건은 다음과 같다.

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

2번과 3번 조건을 보면, 노래 라는 범주 안에서 많이 재생 된 노래를 먼저, 재생된 노래 횟수가 같으면 고유 번호가 낮은 노래를 먼저 수록한다는 점을 알 수 있다.

따라서 우리는 Song 이라는 클래스를 새롭게 선언하여 2, 3번 규칙을 적용할 수 있다.

class Song implements Comparable<Song> {
    int plays;
    int idx;
    
    public Song(int plays, int idx) {
        this.plays = plays;
        this.idx = idx;
    }
    
    @Override
    public int compareTo(Song o) {
        int c = Integer.compare(o.plays, this.plays);
        if (c != 0) {
            return c;
        }
        
        if (c == 0) {
            return Integer.compare(this.idx, o.idx);
        }
        
        return c;
    }
}

c == 0이라는 의미는 재생 횟수인 plays가 같은 경우를 의미한다.

이제 1번 조건인 속한 노래가 많이 재생된 장르를 먼저 수록할 수 있도록 해야한다.

따라서 각 장르별로 모든 노래의 재생 횟수를 담은 해시 자료구조를 사용한다.

HashMap<String, Integer> hashMap = new HashMap<>();
        
for (int i = 0; i < genres.length; i++) {
	hashMap.put(genres[i], hashMap.getOrDefault(genres[i], 0) + plays[i]);
}

우리는 hashMap = [[classic=1450], [pop=3100]]와 같이 장르별 총 재생횟수를 구하였다.

총 재생횟수 별로 장르를 내림차순 하기 위해 아래와 같이 정렬한다.

ArrayList<String> genresList = new ArrayList<>();
for (String genre : hashMap.keySet()) {
	genresList.add(genre);
}
        
genresList.sort((o1, o2) -> hashMap.get(o2) - hashMap.get(o1));

이제 마지막으로 우선순위 큐를 통해 장르별로 노래를 추가해주면 정답을 구할 수 있다.
(우리가 정의한 Song 클래스의 정렬 기준에 맞춰서 우선순위 큐에 들어가기 떄문에 별도로 정렬하는 과정이 필요없다.)

for (String genre : genresList) {
	PriorityQueue<Song> pq = new PriorityQueue<>();
            
	for (int i = 0; i < genres.length; i++) {
    	if (genre.equals(genres[i])) {
        	pq.add(new Song(plays[i], i));
		}
    }
            
    answer.add(pq.poll().idx);
            
    if (pq.size() != 0) {
    	answer.add(pq.poll().idx);
        }
    }
    ...

따라서 전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        HashMap<String, Integer> hashMap = new HashMap<>();
        
        for (int i = 0; i < genres.length; i++) {
            hashMap.put(genres[i], hashMap.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        ArrayList<String> genresList = new ArrayList<>();
        for (String genre : hashMap.keySet()) {
            genresList.add(genre);
        }
        
        genresList.sort((o1, o2) -> hashMap.get(o2) - hashMap.get(o1));
        
        for (String genre : genresList) {
            PriorityQueue<Song> pq = new PriorityQueue<>();
            
            for (int i = 0; i < genres.length; i++) {
                if (genre.equals(genres[i])) {
                    pq.add(new Song(plays[i], i));
                }
            }
            
            answer.add(pq.poll().idx);
            
            if (pq.size() != 0) {
                answer.add(pq.poll().idx);
            }
        }
        
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

class Song implements Comparable<Song> {
    int plays;
    int idx;
    
    public Song(int plays, int idx) {
        this.plays = plays;
        this.idx = idx;
    }
    
    @Override
    public int compareTo(Song o) {
        int c = Integer.compare(o.plays, this.plays);
        if (c != 0) {
            return c;
        }
        
        if (c == 0) {
            return Integer.compare(this.idx, o.idx);
        }
        
        return c;
    }
}

코드를 하나 하나 떼서 보면 크게 어렵지 않을 수 있지만, 해시와 우선순위 큐를 종합적으로 고려해서 적용할 수 있는 지 묻는 문제이므로 난이도가 상당히 높다고 생각한다.

특히, genreList와 같이 해시의 Key를 통해 값을 접근하여, 해당 값을 가지고 장르를 내림차순 정렬하는 방식을 떠올리기가 상당히 어려운 것 같다...