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

이 문제는 3단계치곤 좀 쉬운 축인듯.

장르 별 횟수 합산과, 장르 별 1,2순위의 play의 값들을 저장할 Map을 정의한다.

장르 별 play들의 순위를 유지하기 위해 우선순위 큐를 활용했으며,

poll로 탈락시키기 위해  우선순위 조건은 반대로 설정했다.

그로 인해 genreCountMap의 반복 순서와  poll하여 나열하는 순서를 모두 반대로 진행하였고,

마지막에 역순으로 정렬하여 answer를 반환한다.

 

모든걸 역순으로 진행하는 과정에서 실수가 발생하는걸 막기위해

웬만하면 ArrayDeque등을 사용하고 싶었으나 우선순위를 지원하지않기 때문에

또 다른 구현체를 만들거나 익명클래스를 사용해야 했는데..
그럴 바엔 그냥 꼼꼼하게 잘 확인하면서 그냥 풀기로 했다..

 

import java.util.*;

class Solution {
    Map<String,Long> genreCountMap; // 장르 별 횟수 합산을 위한 Map
    Map<String,PriorityQueue<Song>> songMap;	// 장르 별 우선순위 큐
    
    public int[] solution(String[] genres, int[] plays) {
        
        genreCountMap = new HashMap<>();
        songMap = new HashMap<>();

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

            genreCountMap.put(genre, genreCountMap.getOrDefault(genre, 0L) + play); // 횟수 합산

            PriorityQueue<Song> songQueue = songMap.computeIfAbsent(genre, k -> new PriorityQueue<>( // count와 id로 우선순위 큐 생성.
                (s1, s2) -> {
                    if (s1.count != s2.count) return Integer.compare(s1.count, s2.count);	// poll로 탈락시키기 위해, 우선순위 반대로 설정.
                    return Integer.compare(s2.id, s1.id);
                }));

            songQueue.add(new Song(i, play));  
            while(songQueue.size() > 2){ // 2개까지만 유지
                songQueue.poll(); // 2개 이후 탈락.
            }
        }

        List<Integer> reversedAnswerList = new ArrayList<>();
        //장르별 plays 합산 역순으로 실행.
        genreCountMap.keySet().stream().sorted(Comparator.comparingLong(genreCountMap::get))
            .forEach(genre -> {
                PriorityQueue<Song> songQueue =  songMap.get(genre);
                while(!songQueue.isEmpty()){ // 역순으로 add
                    reversedAnswerList.add(songQueue.poll().id);
                }
            });
        
        int listSize = reversedAnswerList.size();
        int[] answer = new int[listSize];

		// reversedAnswerList 역순으로 정답 도출
        for(int i = 0; i< answer.length; i ++){
            answer[i] = reversedAnswerList.get(listSize -1 - i);
        }

        return answer;

    }
    

    class Song{
        int id;
        int count;

        public Song(int id, int count){
            this.id = id;
            this.count = count;
        }
    }
}

 

 

※ 이후 확인해보니 TreeSet 으로 역순 처리 없이도 구현이 가능했다.

PriorityQueue 또한 배열을 이용해 Tree 구조를 구현한 것이다 보니, 생각해보면 당연한 사실.

TreeSet은 처음과 끝 노드에 모두 접근이 가능하기 때문에 역순으로 돌릴 필요가 없다.

 

하지만 유의할점은 트리의 구현방식이 달라 TreeSet이 더 많은 메모리를 필요로 한다는 것.

PriorityQueue는 내부적으로 배열을 이용해서 Tree를 구현하기 때문에

간선정보 등을 저장하지 않고 자식노드 특정이 가능하지만,

TreeSet 은 내부적으로 Red-Black Tree를 사용하기 때문에, 각 노드를 인스턴스로 저장하고
인스턴스의 색상(R,B) 과 간선정보(자식노드 참조값) 등을 저장해야 하기 때문이다.

허허... 다른 방법을 찾았어도 역시나 그냥 역순으로 낫다!