[99클럽 코테 스터디 1일차 TIL] 프로그래머스 - 베스트앨범

체감 난이도 : 중하

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제분석

• 노래 수록 기준 1을 보면, 장르별 재생 횟수를 알아야합니다.
  : genres, plays에 장르와 재생횟수의 정보가 있기때문에, 이 둘을 합쳐서 봐야합니다.
  : key를 장르명, value를 장르별 재생횟수로 갖는 HashMap을 이용하면 좋을 것 같습니다.

• genres, plays의 길이는 10,000이하이기 때문에, O(N^2)으로 풀면 안될 것 같습니다.

설계

1. HashMap에 장르별 총 재생횟수를 저장합니다. : O(n)
2. 1에서 구한 HashMap을 value값 내림차순으로 정렬합니다. O(nlogn)
3. HashMap<장르명, List<노래 번호, 노래 재생 횟수>>에 장르별로 노래 정보를 담습니다. : O(n)
4. 3에서 구한 HashMap의 value인 List를 정렬합니다.정렬 기준은 다음과 같습니다. : O(100) * O(nlogn)
   4-1. 노래 재생 횟수를 내림차순으로 정렬합니다.
   4-1. 노래 재생 횟수가 같다면, 노래 고유 번호를 오름차순으로 정렬합니다.

총 시간복잡도
O(n) + O(nlogn) + O(n) + O(100) * O(nlogn) = O(nlogn)

코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> result = new ArrayList<>();
        
        HashMap<String, Integer> cntOfGenre = new HashMap<>();
        HashMap<String, List<Info>> music = new HashMap<>(); // 장르명, List<번호, 횟수>
        for (int i = 0; i < genres.length; i++) {
            cntOfGenre.putIfAbsent(genres[i], 0);
            cntOfGenre.replace(genres[i], cntOfGenre.get(genres[i]) + plays[i]);
        }
        
        List<String> keys = new ArrayList(cntOfGenre.keySet());
        Collections.sort(keys, (o1, o2) -> cntOfGenre.get(o2) - cntOfGenre.get(o1)); // 내림차순
        
        for (int i =0; i < genres.length; i++) {
            music.putIfAbsent(genres[i], new ArrayList<Info>());    
            music.get(genres[i]).add(new Info(i, plays[i]));
        }
        
        for(String key : keys) {
            Collections.sort(music.get(key));
        }
        
        for (String key : keys) {
            result.add(music.get(key).get(0).idx);
            
            if (music.get(key).size() > 1) {
                result.add(music.get(key).get(1).idx);
            }
        }
        
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
    
    class Info implements Comparable<Info> {
        int idx;
        int cnt;
        
        public Info(int idx, int cnt) {  
            this.idx = idx;
            this.cnt = cnt;
        }
        
        @Override
        public int compareTo(Info o) {
            if (this.cnt == o.cnt) {
                return this.idx - o.idx;
            }
            
            return o.cnt - this.cnt;
        }
    }
}

공부한 사항

• cntOfGenre.keySet() 은 Set타입으로 추출되는데, 이를 List로 바꾸기 위해서는 new ArrayList(cntOfGenre.keySet()) 를 사용하면 된다.

• Collections.sort(keys, (o1, o2) -> cntOfGenre.get(o2) - cntOfGenre.get(o1));
  : keys를 정렬하는데, cntOfGenre의 값을 기준으로 정렬할 수 있다.

• result.stream().mapToInt(Integer::intValue).toArray();
  : List를 배열로 바꾸기