프로그래머스 베스트앨범 Java + Collection Sort와 Comparator 정리

해시를 잘 사용하여서 풀면 되는 문제였으나 문제를 꼬아놔서 Java로 풀면 Map과 Collection의 특징을 잘 활용하지 못하면 풀지 못하는 문제였습니다. 알고리즘 적으로 어려운 문제는 아니지만 Map과 Comparator를 연습해 볼 수 있는 문제였습니다.

그리고 이번 문제를 풀면서 익힌걸 다시 정리해보겠습니다.. 우선 코드는 아래와 같고 세부 정리는 코드 밑에 적겠습니다.

//이 문제는.. java라 그런진 모르겠는데 노다가 성이 상당히.. 강하군요..

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

class Pair {
    Integer originalKey;
    Integer value;

    public Pair(Integer key, Integer value) {
        this.originalKey = key;
        this.value = value;
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        List<Integer> answerList = new ArrayList<>();

        Map<String, Integer> maps = new LinkedHashMap<>();
        Map<String, List<Pair>> allPairMap = new HashMap<>();


        //맵에 각 장르별 재생수의 합과 각 고유 번호에 따른 재생수를 Map에 저장한다.
        //재생수의 합은 장르마다의 재생수를 정렬하기 위한 기준이다.
        for (int i = 0; i < genres.length; i++) {
            maps.putIfAbsent(genres[i], 0);
            allPairMap.putIfAbsent(genres[i],new ArrayList());
            int now = i;
            maps.computeIfPresent(genres[i],(String key, Integer value) -> value+=plays[now]);
            allPairMap.computeIfPresent(genres[i], (s, pairs) -> {
                //pair 클래스를 추가해준다. Map의 computeIfPresent함수는 key에 해당하는 값을 찾아서 고친 Value의 값을 리턴해줘야 하기 때문에 pair를 추가해준 뒤 리스트를 리턴한다.
                pairs.add(new Pair(now, plays[now]));
                return pairs;
            });
        }


        //LinkedHashMap의 경우는 Map에 집어넣는 순서를 보장한다. 그러나, Map은 List가 아니기 때문에 Map Entry를 스트림으로 정렬한(value기준으로) 것을 List로 collect 해준다.
        List<Map.Entry> list = maps.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())).collect(Collectors.toList());
        List<String> sortedKey = new ArrayList();

        //나중에 꺼낼때 귀찮음을 방지하기 위한 list
        for(Map.Entry<String,Integer> key : list){
            sortedKey.add(key.getKey());
        }
        int genreNum=maps.size();

        //각 키마다 가지고 있는 list를 정렬해준다. 만약에 value가 같다면 original key의 오름차순으로 정렬해준다. (기본은 내림차순)
        for(String keys : maps.keySet()) {
            Collections.sort(allPairMap.get(keys),((o1, o2) -> {
                if(o1.value.compareTo(o2.value)==0) {
                    return o1.originalKey-o2.originalKey;
                } else {
                    return o2.value-o1.value;
                }
            }));
        }


        //각 리스트에서 2개씩 빼온다. 만약 1개라면 1개만 뽑는다.
        for(String key : sortedKey) {
            if(allPairMap.get(key).size()==1) {
                answerList.add(allPairMap.get(key).get(0).originalKey);
            } else {
                for(int i=0;i<2;i++) {
                    answerList.add(allPairMap.get(key).get(i).originalKey);
                }
            }
        }
        answer = new int[answerList.size()];
        for(int i=0;i<answer.length;i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
}

우선 Sort를 보자면 Collection을 정렬할때에는 List를 넣어줘야 하며 정렬을 커스텀 하고 싶다면 Comparator를 활용해야합니다.
요즘은 익명함수를 통해서 표현합니다.

위 문제의 예에서 보자면 다음과 같습니다.

Collections.sort(allPairMap.get(keys),((o1, o2) -> {
                if(o1.value.compareTo(o2.value)==0) {
                    return o1.originalKey-o2.originalKey;
                } else {
                    return o2.value-o1.value;
                }
            }));

Map에서 받아온 value가 Pair Object로 두개의 Integer 값을 가지는 오브젝트 입니다.
Object이기 때문에 Default를 적용시킬 수 없으며 이 문제에서는 재생수가 같은 경우에는 고유 값을 통해서 정렬해야 하기 때문에 overriding을 해줘야 합니다.

Comparator의 compare는 int를 반환한다. 근데 이때에 (o1, o2)이 부분에서는 o2가 list에서 앞부분이가 o1이 뒷부분이다.
-1을 반환 할 때만 두개의 요소를 swap 해준다.
그래서 o1-o2를 리턴하게 되면 뒷 요소가 앞에 요소보다 클 때 바꾼다는 것이기 때문에 오름차순으로 정렬이 되게 되는 것이다.

이 부분을 잘 기억해서 적용시켜야 할 것 같다.