[프로그래머스] 베스트 앨범

---

프로그래머스 Lv3 - 베스트 앨범 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 해시 문제 중 레벨 3 베스트 앨범 문제를 풀이했다.

로직 흐름을 정리하면 아래와 같다.

1. 문제를 풀이하기 위한 Album 클래스 정의 및 생성자, 필드, Getter, Setter 등 작성
2. Key로 장르를, Value로는 앨범의 정보를 저장할 map 생성
3. 첫번째 반복문을 돌며 map에 해당 장르가 있을경우 필요한 정보 업데이트, 없을 경우 삽입
4. map을 리스트로 감싸주어 총 재생 횟수 기준 내림차순 정렬(제일 많이 들은 장르 먼저 정답 배열에 넣기 위함)
5. 두번째 중첩 반복문에서 map을 탐색하며 문제 조건에 맞게 총 재생횟수가 제일 많은 장르 순, 장르 내에서 가장 많은 재생 횟수를 가지고 있는 노래의 고유번호를 정답 배열에 한 장르당 최대 2개까지 정답 배열에 추가
6. 정답 배열 리턴

3단계 문제 풀이는 이번이 처음인데, 구현하는데 정렬 부분에서 조금 애를 먹은 것 같다.
아무래도 맵 안에 클래스, 클래스 안에 또 맵, 해당 맵을 정렬하기 위해 감싸는 리스트 등 자료 구조를 중첩을 복잡하게 쓰니 가독성 면에도 좋지 않고 정렬을 위해 구글링도 해보고, 3중 중첩 반복문도 맘에 들지 않고...
다양하게 생각을 해보고 풀이를 했지만 좀 지저분 한 것 같다...

BestAlbum.java

package com.example.Programmers.Lv3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BestAlbum {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Album> albumMap = new HashMap<>();

        // 반복문을 돌며 장르를 키 값으로하여 해당 장르가 맵에 존재할 경우 필요한 데이터 업데이트, 존재하지 않을 경우 삽입
        for (int i = 0; i < genres.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            map.put(i, plays[i]);
            if (albumMap.containsKey(genres[i])) {
                Album album = albumMap.get(genres[i]);
                // 총 들은 횟수 더해주기
                album.setTotalPlay(album.getTotalPlay() + plays[i]);
                // 고유 번호가 key, 노래 별 들은 횟수가 value
                album.addPlay(map);
                // 내림차순으로 정렬
                album.sortPlays();
                // 업데이트된 값들 반영
                albumMap.replace(genres[i], album);
            } else {
                albumMap.put(genres[i], new Album(plays[i], Arrays.asList(map)));
            }
        }

        List<Map.Entry<String, Album>> list = new ArrayList<Map.Entry<String, Album>>(albumMap.entrySet());

        // 총 재생 횟수를 기준으로 내림차순 정렬(제일 많이 들은 장르 먼저 정답 배열에 넣기 위함)
        Collections.sort(list, new Comparator<Map.Entry<String, Album>>() {
            @Override
            public int compare(Map.Entry<String, Album> o1, Map.Entry<String, Album> o2) {
                return o2.getValue().getTotalPlay().compareTo(o1.getValue().getTotalPlay()); // 내림차순
            }
        });

        // 위에서 내림차순 정렬된 리스트를 순회하며 총 재생 횟수가 제일 많은 장르 중 개별 재생 횟수가 많은 순으로 고유 번호를 최대 2개까지 정답
        // 배열에 넣고,
        // 그 다음 총 재생 횟수가 제일 많은 장르 탐색하여 동일한 작업 수행
        for (Map.Entry<String, Album> m : list) {
            int cnt = 0;
            for (Map<Integer, Integer> p : m.getValue().getPlays()) {
                for (Map.Entry<Integer, Integer> n : p.entrySet()) {
                    if (cnt == 2) {
                        break;
                    }
                    answer.add(n.getKey());
                    cnt++;
                }
            }
        }
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

class Album {
    private Integer totalPlay;
    private List<Map<Integer, Integer>> plays;

    public Album(int totalPlay, List<Map<Integer, Integer>> plays) {
        this.totalPlay = totalPlay;
        this.plays = new ArrayList<>(plays);
    }

    public Integer getTotalPlay() {
        return totalPlay;
    }

    public void setTotalPlay(int totalPlay) {
        this.totalPlay = totalPlay;
    }

    public List<Map<Integer, Integer>> getPlays() {
        return plays;
    }

    public void addPlay(Map<Integer, Integer> play) {
        this.plays.add(play);
    }

    public void sortPlays() {
        this.plays.sort((o1, o2) -> o2.values().iterator().next().compareTo(o1.values().iterator().next()));
    }
}

BestAlbumTest.java

package com.example.Programmers.Lv3;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class BestAlbumTest {
    @Test
    public void testBestAlbum() {
        BestAlbum ba = new BestAlbum();

        int[] result1 = ba.solution(new String[] { "classic", "pop", "classic", "classic", "pop" },
                new int[] { 500, 600, 150, 800, 2500 });
        int[] result2 = ba.solution(new String[] { "classic", "classic", "classic", "classic", "classic" },
                new int[] { 500, 600, 150, 800, 2500 });

        int[] expected1 = new int[] { 4, 1, 3, 0 };
        int[] expected2 = new int[] { 4, 3 };

        assertArrayEquals(expected1, result1);
        assertArrayEquals(expected2, result2);
    }

}