Programmers - Hash [베스트 앨범]

1. 문제

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

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

입출력 예

genresplaysreturn

[classic, pop, classic, classic, pop]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

2. 내풀이

import java.util.*;


class BestAlbum {
    class Song implements Comparable<Song> {
        private String genre;
        private int plays;
        private int songNumber;

        public int getSongNumber() {
            return songNumber;
        }

        public String getGenre() {
            return genre;
        }

        public int getPlays() {
            return plays;
        }

        public Song(String genre, int plays, int songNumber) {
            this.genre = genre;
            this.plays = plays;
            this.songNumber = songNumber;
        }

        // 오름차순 정렬 현재 객체가 우선순위
        @Override
        public int compareTo(Song o) {
            // 만약에 재생수가 같다면 고유넘버를 기준으로 내림차순으로 정렬한다.
            if (o.getPlays() == this.getPlays()) return this.getSongNumber() - o.getSongNumber();
            else return o.getPlays() - this.getPlays();
        }
    }

    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Song> songs = new ArrayList<>();
        HashMap<String, Integer> genrePlays = new HashMap<>();
        for (int i = 0; i < plays.length; i++) {
            songs.add(new Song(genres[i], plays[i], i));
            // 해당장르가 추가가 안되었다면 plays[i]를 넣고 추가가 이미 되어있다면 plays[i]를 더한 것을 저장한다.
           genrePlays.put(genres[i], genrePlays.getOrDefault(genres[i], 0) + plays[i]);
        }
        // songs 정렬
        Collections.sort(songs, (o1, o2) -> {
            // 먼저 장르가 같다면 재생수를 비교해서 오름차순으로 정렬한다.
            if (o1.getGenre().equals(o2.getGenre()))
                return o1.compareTo(o2);
            // 장르가 같지 않다면 장르의 총 재생수를 비교해서 오름차순으로 정렬한다.
            else {
                return genrePlays.get(o2.getGenre()) - genrePlays.get(o1.getGenre());
            }
        });

        // 정답리스트
        ArrayList<Integer> answerList = new ArrayList<>();
        // 앨범 이름, 앨범에 들어있는 곡 갯수
        HashMap<String, Integer> album = new HashMap<>();
        for (Song song : songs) {
            // 앨범에 장르가 포함되어 있지 않다면
            if (!album.containsKey(song.getGenre())) {
                // 앨범에 장르를 넣고 곡갯수를 1로 넣는다.
                album.put(song.getGenre(), 1);
                // 정답리스트에 곡 고유 번호 추가
                answerList.add(song.getSongNumber());
            }
            // 앨범에 장르가 포함되어 있다면
            else {
                // 해당 장르의 곡 갯수
                int genreCnt = album.get(song.getGenre());
                // 해당 장르의 곡 갯수가 2를 넘어간다면 더이상 해당 장르앨범에 곡를 추가하지 않는다.
                if (genreCnt >= 2) continue;
                else {
                    // 곡 갯수가 2를 넘어가지 않는다면 곡갯수 추가 및 정답리스트에 곡 고유 번호 추가
                    album.put(song.getGenre(), genreCnt + 1);
                    answerList.add(song.getSongNumber());
                }
            }
        }

   int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }

    public static void main(String[] args) {
        BestAlbum bestAlbum = new BestAlbum();
        String[] genres = {"a", "b", "z", "a", "a", "a"};
        int[] plays = {500, 150, 2500, 800, 2500, 2500};
        int[] answer = bestAlbum.solution(genres, plays);
        for (int i = 0; i < answer.length; i++) {
            System.out.print(answer[i] + " ");
        }
    }
}

3. 다른 사람 풀이

- 위 코드는 내풀이가 아니라 사실 다른 사람풀이를 내풀이에 넣어 합친 것이다.

 

getOrDefault(a, 0) 이메소드는 a라는 키를 넣고 나서 없으면 기본 값 0을 넣고 있으면 원래 값을 반환하는 함수이다.

나는 여기에 getOrDefault(a, plays[i]) + plays[i]를 넣어서 값이 없는 경우 plays[i]를 넣고 plays[i]더 넣어 값을 두배로 만들었기 때문에 엄청나게 헤메 었다.

4. Tip

- song이라는 객체를 만들어서 HashMap으로 중복을 제거한다.

- HashMap으로 각 장르 마다 plays수를 계산하고

- Songs라는 Song객체를 가지는 ArrayList를 sorting한다.

ArrayList sorting 할때는 Song 객체 안에서 sorting해야하는 경우와

장르를 sorting해야하는 경우를 구분지어야한다.

 

Song 객체 밖 : 장르의 plays로 오름차순으로 장르를 구분한다.

 

Song 객체 안  : 장르로 구분한다음 장르안에서 재생횟수로 오름차순하고 재생횟수가 같다면

고유넘버를 내림차순으로 정렬해야한다.

 

따라서 객체 안의 경우는 Song객체를 Comparable<Song>인터페이스를 상속받아 compareTo()함수를

오버라이딩 하고

 

객체 밖의 경우는

Collections.sort(songs, (o1, o2) -> {

    장르의 plays가 같다면  객체 안의 경우로 : o1.compare(o2);

    같지 않다면 return o2.getPlays() - o1.getPlays()});

이렇게 람다식으로 익명 메소드를 만들어 구현시킨다.

 

이후 앨범에 담을 때는 앨범에 곡이 들어있지 않다면 곡을 넣고 장르당 곡이 많다면

한곡에 두개씩 담는다.