[프로그래머스 LV3] 베스트 앨범 (Hash, 해시)

🧐 LV3. 베스트 앨범

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한 사항

genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=java 

프로그래머스

 

💡 문제 풀이

재밌는 문제였다! 일단 문제 설명만 읽어봤을 때는 쉽게 풀 수 있을 것이라 생각했는데, 막상 풀어보니 생각해야 할 조건이 몇 있었다. 이 문제에서는 Class와 정렬 조건, 그리고 Hash를 사용했다.

 

먼저 정렬 조건에 맞춰서 Class와 compareTo 메소드를 재정의한다.

여기서는 Song 이름의 Class를 정의했고, Comparable 인터페이스를 구현해주는 방식으로 코드를 작성했다.

    static Map<String, Integer> genreTotalPlay;
    
    static class Song implements Comparable<Song> {
        int id;
        String genre;
        int playCnt;
        
        Song(int id, String genre, int playCnt) {
            this.id = id;
            this.genre = genre;
            this.playCnt = playCnt;
        }
        
        @Override
        public int compareTo(Song o) {
            if (genreTotalPlay.get(this.genre) == genreTotalPlay.get(o.genre)) {
                if (this.playCnt == o.playCnt) {
                    return this.id - o.id;
                }
                return o.playCnt - this.playCnt;
            }
            return genreTotalPlay.get(o.genre) - genreTotalPlay.get(this.genre);
        }
        
    }

여기서 genreTotalPlay는 장르의 전체 재생 수 정보를 저장하고 있는 HashMap 변수이다.

정렬 조건은 다음과 같다.

전역 Map 타입 변수를 사용해서, 장르의 전체 재생 수(genreTotalPlay.get(Song.genre))를 먼저 비교해서 내림차순 정렬한다.

장르(장르의 전체 재생 수)가 같다면, 노래의 재생 수(Song.playCnt)를 비교해서 내림차순 정렬한다.

노래의 재생 수도 같다면, 고유 번호(id)를 비교해서 오름차순 정렬한다.

 

클래스를 정의했으면, 이제 장르 전체 재생 수를 전역 Hash 변수에 저장해주고, 각 노래를 리스트 저장 및 정렬해준다.

        genreTotalPlay = new HashMap<>(); // 장르 전체 재생 수(전역 변수)
        List<Song> songs = new ArrayList<>(); // 노래 정보 리스트
        
        for (int i = 0; i < genres.length; i++) {
            if (!genreTotalPlay.containsKey(genres[i])) genreTotalPlay.put(genres[i], 0);
            genreTotalPlay.put(genres[i], genreTotalPlay.get(genres[i]) + plays[i]);
            songs.add(new Song(i, genres[i], plays[i]));
        }
        
        Collections.sort(songs);

genres와 plays 배열을 돌면서 "장르 전체 재생 수(genreTotalPlay)"와 "노래 정보 리스트(songs)" 변수를 업데이트 해준다.

반복문 종료 후, 리스트를 정렬하면 위에서 재정의한 정렬 조건을 기반으로 정렬된다.

 

마지막 남은 문제의 조건이 있다. "같은 장르에서 최대 2개의 노래만 수록한다"는 조건이다. 이 조건을 만족하기 위해서 위에서 저장한 songs 리스트에서 같은 장르의 최대 2개의 노래만 남아있도록 필터링해주어야 한다. 이 또한 HashMap 변수를 사용해서, 같은 장르에 대해서 3번째 노래부터는 걸러주면 된다.

        Map<String, Integer> genreCount = new HashMap<>();
        List<Integer> album = new ArrayList<>();
        
        for (Song song : songs) {
            if (!genreCount.containsKey(song.genre)) genreCount.put(song.genre, 0);
            if (genreCount.get(song.genre) >= 2) continue;
            genreCount.put(song.genre, genreCount.get(song.genre) + 1);
            album.add(song.id);
        }

genreCount 변수를 활용해서 같은 장르에 대해 선두에 있는 최대 2개의 노래만 album 리스트에 저장해준다. 이미 앞에서 조건에 따라 정렬했으므로 순서대로 판단하면 된다.

 

위 풀이 방법을 전체 코드로 풀어내면 아래와 같다.

import java.util.*;

class Solution {
    
    static Map<String, Integer> genreTotalPlay;
    
    static class Song implements Comparable<Song> {
        int id;
        String genre;
        int playCnt;
        
        Song(int id, String genre, int playCnt) {
            this.id = id;
            this.genre = genre;
            this.playCnt = playCnt;
        }
        
        @Override
        public int compareTo(Song o) {
            if (genreTotalPlay.get(this.genre) == genreTotalPlay.get(o.genre)) {
                if (this.playCnt == o.playCnt) {
                    return this.id - o.id;
                }
                return o.playCnt - this.playCnt;
            }
            return genreTotalPlay.get(o.genre) - genreTotalPlay.get(this.genre);
        }
        
    }
    
    public int[] solution(String[] genres, int[] plays) {
        // 장르의 전체 재생 수 구하기 & 노래 순서 정렬하기
        genreTotalPlay = new HashMap<>();
        List<Song> songs = new ArrayList<>();
        
        for (int i = 0; i < genres.length; i++) {
            if (!genreTotalPlay.containsKey(genres[i])) genreTotalPlay.put(genres[i], 0);
            genreTotalPlay.put(genres[i], genreTotalPlay.get(genres[i]) + plays[i]);
            songs.add(new Song(i, genres[i], plays[i]));
        }
        
        Collections.sort(songs);
        
        // 같은 장르 최대 2개까지만 노래 수록하기
        Map<String, Integer> genreCount = new HashMap<>();
        List<Integer> album = new ArrayList<>();
        
        for (Song song : songs) {
            if (!genreCount.containsKey(song.genre)) genreCount.put(song.genre, 0);
            if (genreCount.get(song.genre) >= 2) continue;
            genreCount.put(song.genre, genreCount.get(song.genre) + 1);
            album.add(song.id);
        }
        
        // ArrayList to Array 변환
        int[] answer = new int[album.size()];
        for (int i = 0; i < album.size(); i++) {
            answer[i] = album.get(i);
        }
        
        return answer;
    }
}

 

✨ 포스팅을 마치며

클래스를 활용해서 정렬 조건을 재정의하고, 답을 도출해내는 과정이 재밌었다. 언제부턴가 알고리즘 문제에서도 클래스 정의를 적극 활용하고 있는데, 가독성도 좋아지고 활용도도 좋은 것 같다. 👍