[프로그래머스/해시] Level 3 베스트앨범 (JAVA)

문제

---

풀이 (2021.01.21)

1. genreCounts HashMap에 장르별 전체 play 카운트를 저장하고, songsPerGenre HashMap에는 장르별 곡을 ArrayList로 저장한다.
2. genreCounts를 play 카운트에 따라 내림차순으로 정렬한다.
3. 각 장르마다 songsPerGenre에 저장된 곡 Arraylist를 탐색하며 최다 재생 2곡(혹은 1곡)을 찾는다.
4. ArrayList를 array로 변환하여 리턴한다.

Song 클래스를 만들어서 정답으로 리턴해야 하는 index, 곡의 genre, 그리고 내림차순 정렬을 위한 play를 필드로 갖도록 했다.

특히 좀 더 효율적으로 HashMap을 초기화하기 위해 노력했다. 아래 songsPerGenre에 ArrayList로 곡들을 추가하는 코드가 맘에 들지 않는데, 새 ArrayList를 만들어 추가하는 다른 방법을 몰라서 코드를 저렇게 짰다.

정답을 찾는 과정은 stream 안에서 해결했다. 마지막에 리턴하는 부분에서도 stream을 사용했는데, 바로 떠오르지 않아서 고민을 좀 했었다. stream을 더 잘 활용하고 싶다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> genreCounts = new HashMap<>();
        Map<String, ArrayList<Song>> songsPerGenre = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            genreCounts.put(genres[i], genreCounts.getOrDefault(genres[i], 0) + plays[i]);
            if (!songsPerGenre.containsKey(genres[i])) {
                ArrayList<Song> newGenre = new ArrayList<>();
                newGenre.add(new Song(i, genres[i], plays[i]));
                songsPerGenre.put(genres[i], newGenre);
            } else songsPerGenre.get(genres[i]).add(new Song(i, genres[i], plays[i]));
        }

        ArrayList<Integer> answer = new ArrayList<>();
        genreCounts.entrySet().stream()
                .sorted(Comparator.comparingInt(entry -> -entry.getValue()))
                .forEach(entry -> {
                    ArrayList<Song> targets = songsPerGenre.get(entry.getKey());
                    targets.sort(Comparator.comparingInt(o -> -o.play));
                    answer.add(targets.get(0).index);
                    if (targets.size() > 1) answer.add(targets.get(1).index);
                });
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}


class Song {

    int index;
    String genre;
    int play;

    public Song(int index, String genre, int play) {
        this.index = index;
        this.genre = genre;
        this.play = play;
    }
}

---

2차 풀이 (2021.08.24)

Song 클래스를 만들어서 짤까 하다가.. 알고리즘 문제를 굳이 객체지향적으로 풀려고 노력하지는 않아도 된다는 생각에 Collection들을 조합해서 풀이했다.

문제를 해결하기 위해서는 두 가지를 찾아야 한다.

1. 장르별 play count sum 내림차순 정렬
2. 장르 내에서 play count 내림차순 정렬

그래서

1. countPerGenre: 장르별 play count sum
2. songsPerGenre: 장르 내 곡들을 play count 내림차순 정렬

이렇게 두 가지 자료구조를 활용했다.

특히 songsPerGenre는 내림차순 PriorityQueue를 적용해서, answer를 찾을 때 O(1)으로 동작하도록 만들었다.

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int n = genres.length;
        
        Set<String> distinctGenres = new HashSet<>();
        Map<String, Integer> countPerGenre = new HashMap<>();
        Map<String, PriorityQueue<Integer>> songsPerGenre = new HashMap<>();
        
        for (String each : genres) {
            distinctGenres.add(each);
            songsPerGenre.put(each, new PriorityQueue<>((o1, o2) -> plays[o2] - plays[o1]));
        }
        
        for (int i=0 ; i<n ; i++) {
            countPerGenre.put(genres[i], countPerGenre.getOrDefault(genres[i], 0) + plays[i]);
            songsPerGenre.get(genres[i]).offer(i);
        }
        
        List<String> genresInOrder = new ArrayList<>(distinctGenres);
        Collections.sort(genresInOrder, (o1, o2) -> countPerGenre.get(o2) - countPerGenre.get(o1));
        
        List<Integer> answer = new ArrayList<>();
        for (String genre : genresInOrder) {
            PriorityQueue<Integer> pq = songsPerGenre.get(genre);
            answer.add(pq.poll());
            if (!pq.isEmpty()) {
                answer.add(pq.poll());
            }
        }
        
        return answer.stream().mapToInt(Integer::valueOf).toArray();
    }
}