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

🔗 문제 링크

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

코딩테스트 연습 - 베스트앨범

 

📝 풀이 과정

genreTimes.put(genres[i], genreTimes.getOrDefault(genres[i], 0) + plays[i]);

먼저 장르마다 총 누적 플레이시간을 저장해야하기 때문에 Map.getOrDefault()를 통해 Map에 해당 장르가 존재한다면 기존 값을 얻어와 더해 다시 덮어쓰기 해주고 아니라면 0을 반환해 현재 값을 추가해 넣도록 하였다.

 

 

List<Map.Entry<String, Integer>> list = new ArrayList<>(genreTimes.entrySet());
Collections.sort(list, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));

장르의 총 누적합이 계산되면 누적합을 기준으로 정렬을 해야하는데 Map에서 Value 기준의 정렬이 불가능하기 때문에 Map을 List<Map.Entry<K,V>>형태로 변환해 주었다. Collections.sort를 활용해 Entry의 value를 기준으로 내림차순 정렬했다. 정렬한 List를 기준으로 각 장르마다 플레이타임, 고유번호로 정렬해 추출하는 것을 어떻게 해야할까 고민하던 중 PriorityQueue를 사용하기로 했다.

 

 

genreMap.computeIfAbsent(genres[i], k ->
                    new PriorityQueue<>((o1, o2) -> o1[1] != o2[1] ? Integer.compare(o2[1], o1[1]) : Integer.compare(o1[0], o2[0])))
                    .add(new int[]{i, plays[i]});

Map<String, PriorityQueue>>를 사용해 장르를 Key로 넣어주고, PrioriryQueue는 int배열 형태로 {고유번호, 플레이타임}을 넣어 플레이타임 내림차순, 고유번호 오름차순 순으로 정렬하였다.

또한, Map.computeIfAbsent를 활용해 만약 해당하는 장르가 Map에 존재하지 않는다면 새로 PriorityQueue를 생성해 Map에 넣어주고 해당 Queue에 추가해주었다.

 

 

List<Integer> ans = new ArrayList<>();
for (Map.Entry<String, Integer> entry : list) {
  int cnt = 0;
  PriorityQueue<int[]> que = genreMap.get(entry.getKey());

  while (!que.isEmpty() && cnt < 2) {
    ans.add(que.poll()[0]);
    cnt++;
  }
}

이후, 총 플레이리스트가 얼마나 생성될 지 길이를 알지 못하기 때문에 List로 생성해주었다. Queue가 비었거나 cnt가 2가 되지 않을 때까지 List에 넣어주고 return할 때 List를 int[]로 변환해 반환해준다.

 

💻 코드

import java.util.*;

public class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int N = genres.length;
        Map<String, Integer> genreTimes = new HashMap<>();
        Map<String, PriorityQueue<int[]>> genreMap = new HashMap<>();

        for (int i = 0; i < N; i++) {
            genreTimes.put(genres[i], genreTimes.getOrDefault(genres[i], 0) + plays[i]);
            genreMap.computeIfAbsent(genres[i], k ->
                    new PriorityQueue<>((o1, o2) -> o1[1] != o2[1] ? Integer.compare(o2[1], o1[1]) : Integer.compare(o1[0], o2[0]))).add(new int[]{i, plays[i]});
        }

        List<Map.Entry<String, Integer>> list = new ArrayList<>(genreTimes.entrySet());
        Collections.sort(list, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));

        List<Integer> ans = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : list) {
            int cnt = 0;
            PriorityQueue<int[]> que = genreMap.get(entry.getKey());

            while (!que.isEmpty() && cnt < 2) {
                ans.add(que.poll()[0]);
                cnt++;
            }
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}