프로그래머스 - 베스트 앨범

베스트 앨범 : https://school.programmers.co.kr/learn/courses/30/lessons/42579

---

Problem

---

Solve

수록 기준
1. 많이 재생된 장르
2. 장르 내에서 많이 재생된 노래
3. 같은 장르내에서 많이 재생된 노래가 같다면 고유 번호가 작은 노래
를 기준으로 정렬된 값으로 나열되다보니 PriorityQueue로 풀어보았다.

풀이 순서
Map<String, Integer> playOfGenre : 각 장르의 합산 재생 시간
Map<String, PriorityQueue< Music >> musicOfGenre : 각 장르의 노래 (1순위 정렬 : 재생된 횟수 내림차순, 2순위 정렬 : 고유 번호 오름차순) 을 준비한다.

1. genres를 돌변서 playOfGenre에 해당 장르의 재생 시간에 plays[i]를 더해준다.

   • 그리고 musicOfGenre에 new Music(i, plays[i])를 저장해준다.

2. playOfGenre에서 재생 시간이 큰 순으로 장르를 정렬하기 위해 PriorityQueue< Genre > pq를 만들어 저장해준다.

3. pq에서 하나씩 빼오면서 해당 장르의 노래를 돌면서 최대 2개씩 list에 저장한다.

   • pq가 정렬이 되기 위해 poll()을 꼭 해주어야 한다.

---

Code

import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
    	//장르 별 총합 재생 시간
        Map<String, Integer> playOfGenre = new HashMap<>();
        //장르 별 노래 정보
		Map<String, PriorityQueue<Music>> musicOfGenre = new HashMap<>();

		for (int i = 0; i < genres.length; i++) {
			String genre = genres[i];
			int play = plays[i];

			//해당 장르의 재생 시간 갱신
			playOfGenre.put(genre, playOfGenre.getOrDefault(genre, 0) + play);

			//해당 장르에 노래 정보(Music) 추가
			if (!musicOfGenre.containsKey(genre)) {
				musicOfGenre.put(genre, new PriorityQueue<>());
			}
			musicOfGenre.get(genre).offer(new Music(i, play));
		}

		//재생 시간 내림차순으로 장르를 정렬하기 위한 PQ
		PriorityQueue<Genre> pq = new PriorityQueue<>();
		for (String g : playOfGenre.keySet()) {
			pq.offer(new Genre(g, playOfGenre.get(g)));
		}

		List<Integer> list = new ArrayList<>();
		int size = pq.size();
        //재생 시간으로 정렬된 장르 반복
		for (int i=0;i<size;i++) {
			Genre g = pq.poll();
			PriorityQueue<Music> musicPQ = musicOfGenre.get(g.genre);

			//해당 장르에서 최대 2개의 노래를 추가해주며 1개일 경우 1개만 반환하도록한다.
			for (int j = 0; j < 2; j++) {
				if (!musicPQ.isEmpty()) {
					list.add(musicPQ.poll().idx);
				}
			}
		}

		return list.stream().mapToInt(Integer::new).toArray();
    }
    
    //1순위 정렬 : 재생시간 내림차순, 2순위 정렬 : 고유 번호 오름차순
    class Music implements Comparable<Music>{
		int idx;
		int play;
		Music(int idx, int play){
			this.idx = idx;
			this.play = play;
		}

		@Override
		public int compareTo(Music o){
			int result = o.play - this.play;
			if(result == 0){
				result = this.idx - o.idx;
			}
			return result;
		}
	}

	//장르 정렬 : 총 재생 시간 내림차순
	class Genre implements Comparable<Genre> {
		String genre;
		int totalPlay;
		public Genre(String genre, int totalPlay){
			this.genre = genre;
			this.totalPlay = totalPlay;
		}

		@Override
		public int compareTo(Genre o1){
			return o1.totalPlay - this.totalPlay;
		}
	}
}

---

Result

우선순위 큐에 대해 잘못알고 있어서 문제해결이 조금 오래걸렸다.
지금까지는 우선순위 큐에 넣으면 넣을때마다 정렬이 되는 줄 알았는데, 삽입, 삭제시 최소값이나 최대값만 root로 정렬되는 것이지 전체 값이 정렬되어 있는 것이 아니다. (허허..)

---

Reference