EunSung.log

베스트앨범

4 min read

문제 정보

풀이

구현의 비중이 큰 문제다.

우선 문제에서 제시된 조건을 정리하면 다음과 같다.

  1. 속한 노래가 많이 재생된 장르를 먼저 수록
  2. 장르 내에서 많이 재생된 노래를 먼저 수록
  3. 재생 횟수가 같다면 고유 번호가 낮은 노래를 먼저 수록

1번 조건을 만족하기 위해서 장르 별 재생 횟수를 저장하는 해시맵 genreTotalPlay를 선언했다. (key = 장르명, value = 재생 횟수)

또한, 2번 조건을 만족하기 위해 각 장르 내 음악에 대한 정보를 저장하는 해시맵 music을 선언했다. (key = 장르명, value = int형 배열{고유 번호, 재생 횟수}을 저장하는 리스트)

입력으로 들어온 genres를 순회하며 genreTotalPlay와 music에 값을 삽입한다.

그 후, music.keySet()을 순회하며 각 key에 대한 값, 즉 int 배열을 재생 횟수를 기준으로 정렬했다. (2번 조건 만족을 위함)

그 후 장르 별 재생 횟수를 기준으로 정렬해야 하는데, 해시맵은 정렬이 불가능한 비선형 자료구조이므로 sortedGenre 라는 String 리스트를 선언했다.

sortedGenre에 장르명을 모두 삽입한 다음, genreTotalPlay의 값을 기준으로 sortedGenre를 정렬했다.

이후엔 sortedGenre를 순회하면서 음악의 고유 번호를 삽입하면 된다.

코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genreTotalPlay = new HashMap<>();
        HashMap<String, List<int[]>> music = new HashMap<>();
        
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];
            
            genreTotalPlay.put(genre, genreTotalPlay.getOrDefault(genre, 0) + play);
            
            music.putIfAbsent(genre, new ArrayList<>());
            music.get(genre).add(new int[]{i, play});
        }
        
        for (String key : music.keySet()) 
            music.get(key).sort((m1, m2) -> {
            if (m1[1] != m2[1]) // 재생 횟수가 다르면
                return Integer.compare(m2[1], m1[1]); // 재생 횟수 내림차순 정렬
            return Integer.compare(m1[0], m2[0]); // 고유 번호 오름차순 정렬
        });
        
        List<String> sortedGenre = new ArrayList<>(genreTotalPlay.keySet());
        sortedGenre.sort((g1, g2) -> Integer.compare(genreTotalPlay.get(g2), genreTotalPlay.get(g1)));
        
        List<Integer> answer = new ArrayList<>();
        
        for (String genre : sortedGenre) {
            List<int[]> musics = music.get(genre);
            
            answer.add(musics.get(0)[0]);
            
            if (musics.size() > 1)
                answer.add(musics.get(1)[0]);
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

음악 고유 번호 기준 오름차순 정렬에 대해

for (String key : music.keySet()) 
    music.get(key).sort((m1, m2) -> {
    if (m1[1] != m2[1]) // 재생 횟수가 다르면
        return Integer.compare(m2[1], m1[1]); // 재생 횟수 내림차순 정렬
    return Integer.compare(m1[0], m2[0]); // 고유 번호 오름차순 정렬
	});

위의 return Integer.compare(m1[0], m2[0]); 부분은 사실 없어도 통과는 된다. 즉 다음처럼 작성하고 제출해도 된다.

for (String key : music.keySet())
	music.get(key).sort((m1, m2) -> Integer.compare(m2[1], m1[1]));

ArrayList에 삽입되는 순서가 고유 번호 순서와 동일하고, Java의 sort는 안정 정렬1이기 때문이다.

그러나 동작을 드러내기 위해서 고유 번호 기준 오름차순 정렬을 명시적으로 작성했다.

Footnotes

  1. 값이 동일한 원소가 여러 개 존재하는 경우, 해당 원소들의 상대적인 위치가 정렬 후에도 바뀌지 않는 정렬 ↩

백링크