[PGS / Hash] 베스트앨범 (java)

문제 보기

문제

• 입력 : 노래별 장르 genres[], 노래별 재생 횟수 plays[]
• 출력 : 재생수 높은 순으로, 장르별로 가장 많이 들은 노래 2개씩 모은 배열 answer

문제 풀이

필요 데이터는
1. 장르 종류, 장르별 총 재생 횟수
2. 장르별 곡들의 고유 번호, 재생 횟수 이다.

1. key : 장르 종류, value : 장르별 총 재생 횟수
2. key : 장르 종류, value : 곡들의 고유 번호, 재생 횟수
   • key : 곡 고유번호, value : 곡 재생 횟수

총 2개의 해시맵을 생성하여 필요 데이터를 저장한다.

문제 예시와 같이 확인하면, 다음과 같은 형태로
1. HashMap<String, Integer> sum
2. HashMap<String, HashMap<Integer, Integer>> music

총 2개의 HashMap을 필요로 하고, 모두 데이터 삽입 이후 재생수 내림차순으로 정렬을 해야한다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

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

        // 장르별 재생 수 합계
        HashMap<String, Integer> sum = new HashMap<>();

        // 장르별 곡 고유번호와 재생 수 저장
        HashMap<String, HashMap<Integer, Integer>> music = new HashMap<>();

        // 장르별로 재생 수와 곡 정보 저장
        for (int i = 0; i < genres.length; i++) {
            // 장르별 재생 수 합계 업데이트
            if (sum.containsKey(genres[i])) {
                sum.put(genres[i], sum.get(genres[i]) + plays[i]);
                music.get(genres[i]).put(i, plays[i]);
            } else {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(i, plays[i]);
                music.put(genres[i], map);
                sum.put(genres[i], plays[i]);
            }
        }

        // 장르별 재생 수 내림차순으로 정렬
        List<String> key_set = new ArrayList<>(sum.keySet());
        Collections.sort(key_set, (o1, o2) -> sum.get(o2) - sum.get(o1)); // 장르 재생 수에 따른 정렬

        // 정렬된 장르 순으로 곡의 고유 번호를 추가
        for (String key : key_set) {
            HashMap<Integer, Integer> map = music.get(key);

            // 해당 장르에서 곡들을 재생 수 내림차순으로 정렬
            List<Integer> genreKey = new ArrayList<>(map.keySet());
            Collections.sort(genreKey, (o1, o2) -> map.get(o2) - map.get(o1)); // 재생 수에 따라 정렬

            // 해당 장르에서 가장 많이 재생된 두 곡을 추가
            answer.add(genreKey.get(0));
            if (genreKey.size() > 1) {
                answer.add(genreKey.get(1));
            }
        }
        
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

성능 검사

1. 장르별 재생 수 합계 및 장르별 곡 저장
   n번 순회 (for문) -> O(n)
2. 장르별 재생 수 내림차순 정렬
   Collections.sort는 O(mlogm)의 시간 복잡도를 가진다.
   (m : 장르의 갯수 )
3. 각 장르에서 곡 재생 수 기준으로 정렬 및 고유 번호 저장
   m번 순회 (for문)
   Collections.sort 사용으로 O(klogk)의 시간이 소요되지만, (k : 장르 별 곡 수 ) 최악의 경우 모든 곡이 한 장르에 속할 경우 O(nlogn)의 시간 복잡도를 갖는다.

=> O(nlogn)