프로그래머스 - 베스트 앨범 (JAVA)

프로그래머스 베스트 앨범 풀이 과정
해시 카테고리 문제인데, 정렬 기준이 여러 개라 꽤 헤맸다.
총 3번의 제출 끝에 통과

---

1트 (오답)

→ 장르별 총 스트리밍 횟수를 genMap에 저장하고, TreeMap의 Key 기준 역순 정렬로 장르 순서를 정하려 했다.
→ 각 곡의 인덱스는 playIdx에 plays[i] → i 형태로 저장했다.

import java.util.*;
// 음악 클래스
class Music implements Comparable<Music> {
    String genre;
    int play;

    public Music(String genre, int play) {
        this.genre = genre;
        this.play = play;
    }

    @Override
    public int compareTo(Music m) {
        return m.play - this.play;
    }
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> genMap = new HashMap<>(); // 장르별 스트리밍 횟수 저장
        Map<Integer, Integer> playIdx = new HashMap<>(); // 스트리밍 횟수 인덱스 저장
        List<Music> playlist = new ArrayList<>(); // 곡별 스트리밍 횟수 저장

        for(int i=0; i<plays.length; i++) {
            genMap.put(genres[i], genMap.getOrDefault(genres[i],0) + plays[i]);
            playIdx.put(plays[i], i);
            playlist.add(new Music(genres[i], plays[i]));
        }

        // 새로 알게 된 개념 -> Key 기준으로 정렬
        Map<String, Integer> genSort = new TreeMap<>(Collections.reverseOrder());
        genSort.putAll(genMap);

        // 리스트에 장르별 베스트 2개 담기
        List<Integer> list = new ArrayList<>();

        for(Map.Entry<String, Integer> gen : genSort.entrySet()) {
            List<Music> tmp = new ArrayList<>();

            for(Music m : playlist) {
                if(gen.getKey().equals(m.genre)) tmp.add(m);
            }

            Collections.sort(tmp);

            if(tmp.size() == 1) {
                list.add(playIdx.get(tmp.get(0).play));
            }
            else {
                list.add(playIdx.get(tmp.get(0).play));
                list.add(playIdx.get(tmp.get(1).play));
            }
        }

        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) answer[i] = list.get(i);

        return answer;
    }
}

위 풀이의 결과

• TreeMap의 역순 정렬은 Key(장르 이름) 알파벳 기준으로 정렬하는 것이라, 총 스트리밍 횟수 기준 정렬과 전혀 관계없다. 장르 순서가 완전히 잘못됐다.
• playIdx에 plays[i] → i를 저장하는 방식은 같은 스트리밍 횟수를 가진 곡이 있으면 덮어씌워진다. 인덱스를 제대로 추적할 수 없는 구조다.
• 히스토리 기준으로 20점 구간에 해당하는 풀이다.

---

2트 (오답)

→ playIdx의 덮어쓰기 문제를 인식하고, Music 객체에 인덱스(idx)를 직접 포함시켜 playIdx Map을 완전히 제거했다.
→ 덕분에 같은 스트리밍 횟수의 곡이 있어도 인덱스를 잃지 않게 됐다.
→ 그러나 장르 정렬 방식은 그대로 TreeMap(Collections.reverseOrder())를 유지했다. 이 부분이 여전히 문제임을 아직 파악하지 못한 상태였다.

import java.util.*;
// 음악 클래스
class Music implements Comparable<Music> {
    String genre;
    int play;
    int idx; // idx 필드 추가

    public Music(String genre, int play, int idx) {
        this.genre = genre;
        this.play = play;
        this.idx = idx;
    }

    @Override
    public int compareTo(Music m) {
        return m.play - this.play;
    }
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> genMap = new HashMap<>(); // 장르별 스트리밍 횟수 저장
        List<Music> playlist = new ArrayList<>(); // 곡별 스트리밍 횟수 저장

        for(int i=0; i<plays.length; i++) {
            genMap.put(genres[i], genMap.getOrDefault(genres[i],0) + plays[i]);
            playlist.add(new Music(genres[i], plays[i], i)); // playIdx 제거, idx를 객체에 직접 포함
        }

        // Key 기준 역순 정렬 (문제 있음 - 아직 미수정)
        Map<String, Integer> genSort = new TreeMap<>(Collections.reverseOrder());
        genSort.putAll(genMap);

        // 리스트에 장르별 베스트 2개 담기
        List<Integer> list = new ArrayList<>();

        for(Map.Entry<String, Integer> gen : genSort.entrySet()) {
            List<Music> tmp = new ArrayList<>();

            for(Music m : playlist) {
                if(gen.getKey().equals(m.genre)) tmp.add(m);
            }

            Collections.sort(tmp);

            if(tmp.size() == 1) {
                list.add(tmp.get(0).idx); // playIdx 대신 객체의 idx 직접 참조
            }
            else {
                list.add(tmp.get(0).idx);
                list.add(tmp.get(1).idx);
            }
        }

        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) answer[i] = list.get(i);

        return answer;
    }
}

위 풀이의 결과

• playIdx 덮어쓰기 문제는 해결됐다. Music 객체에 idx를 포함시킨 덕분에 인덱스 추적은 이제 정확하다.
• 하지만 TreeMap(Collections.reverseOrder())는 Key인 장르 이름의 알파벳 역순으로 정렬한다. genMap의 Value(총 스트리밍 횟수)와는 아무 관계가 없어서 장르 순서가 여전히 틀렸다.
• 히스토리 기준 13.3점 구간.

---

3트 (정답)

→ TreeMap Key 정렬 문제를 마침내 파악했다. 장르 정렬을 Value(총 스트리밍 횟수) 기준으로 바꿨다.
→ keySet을 꺼내 Comparator로 커스텀 정렬하는 방식으로 수정했다.

import java.util.*;
// 음악 클래스
class Music implements Comparable<Music> {
    String genre;
    int play;
    int idx;

    public Music(String genre, int play, int idx) {
        this.genre = genre;
        this.play = play;
        this.idx = idx;
    }

    @Override
    public int compareTo(Music m) {
        return m.play - this.play;
    }
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> genMap = new HashMap<>(); // 장르별 스트리밍 횟수 저장
        List<Music> playlist = new ArrayList<>(); // 곡별 스트리밍 횟수 저장

        for(int i=0; i<plays.length; i++) {
            genMap.put(genres[i], genMap.getOrDefault(genres[i],0) + plays[i]);
            playlist.add(new Music(genres[i], plays[i], i));
        }

        // Value 기준으로 정렬
        List<String> keySet = new ArrayList<>(genMap.keySet());
        keySet.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return genMap.get(o2) - genMap.get(o1);
            }
        });

        // 리스트에 장르별 베스트 2개 담기
        List<Integer> list = new ArrayList<>();

        for(String gen : keySet) {
            List<Music> tmp = new ArrayList<>();

            for(Music m : playlist) {
                if(gen.equals(m.genre)) tmp.add(m);
            }

            Collections.sort(tmp);

            if(tmp.size() == 1) {
                list.add(tmp.get(0).idx);
            }
            else {
                list.add(tmp.get(0).idx);
                list.add(tmp.get(1).idx);
            }
        }

        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) answer[i] = list.get(i);

        return answer;
    }
}

위 풀이의 결과

• genMap.keySet()을 꺼내 Comparator로 Value 기준 내림차순 정렬 → 장르 순서가 정확히 잡혔다.
• Music 객체에 idx를 포함시켜 같은 재생 횟수여도 인덱스를 잃지 않는다.
• 정확성 테스트 통과

---

3번의 시도를 돌아보면, 1트에서 2트로 넘어갈 때는 playIdx 덮어쓰기 문제를 잡았고, 2트에서 3트로 넘어갈 때는 TreeMap(reverseOrder())이 Key 알파벳 정렬임을 뒤늦게 깨달았다. 두 문제를 한 번에 잡지 못하고 한 번씩 나눠서 틀린 셈이다.
핵심은 "정렬 기준이 Value일 때는 keySet을 꺼내 Comparator로 직접 정렬" 하는 것, 그리고 "객체에 인덱스를 처음부터 포함시키는 것" 이다. 다음엔 더 빠르게 보이길 바라며.