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

🤔 문제

🔗

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

💡 풀이과정

해싱과 정렬을 사용하는 문제이다.

모든 노래를 리스트에 담아 정렬한 후 리스트를 순회하며 장르마다 노래를 두개씩 뽑아내는 방식으로 풀면 된다.

 

우선, Music 클래스를 작성해보자.

class Music implements Comparable<Music> {
    int id;
    int genre;
    int play;

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

    @Override
    public int compareTo(Music m) {
        if(this.genre!=m.genre) return m.genre-this.genre;
        else if(this.play!=m.play) return m.play-this.play;
        else return this.id-m.id;
    }
}

정렬을 위해 Comparable<T> 인터페이스를 상속했다.

문제에서 제시한 정렬 순서는 장르->재생 횟수->고유 번호이기 때문에 이 순서로 정렬하는 compareTo()를 구현한다.

 

장르 타입을 String이 아닌 int로 지정한 것은, 장르는 장르 내 속한 노래의 재생횟수 총합에 따라 순서가 때문이다.

따라서 리스트에 노래를 담기 전, 장르 별 재생횟수를 구해 장르 이름 대신 이 값을 삽입해주어야 한다.

 

이제 HashMap을 통해 장르별 재생횟수를 구한다.

HashMap<String, Integer> map = new HashMap();

for(int i=0 ; i<genres.length ; i++) {
    if(map.containsKey(genres[i])) {
        map.put(genres[i], map.get(genres[i])+plays[i]);
    } else {
        map.put(genres[i], plays[i]);
    }
}

 

ArrayList에 노래를 담고 정렬한다.

앞서 설명한대로 장르 이름 대신 map에서 구한 재생횟수를 삽입한다.

ArrayList<Music> musicList = new ArrayList();

for(int i=0 ; i<genres.length ; i++) {
    Music m = new Music(i, map.get(genres[i]), plays[i]);
    musicList.add(m);
}
Collections.sort(musicList);

 

마지막으로 Iterator를 사용해 배열을 순회해 각 장르마다 노래를 두개씩 꺼낸다.

ArrayList<Integer> bestList = new ArrayList();

int c = 0;	// 카운트
int g = 0;	// 현재 장르 정보
Iterator<Music> it = musicList.iterator();

while(it.hasNext()) {
    Music m = it.next();
    c++;
    if(g==m.genre) {
        if(c<2) {
            bestList.add(m.id);
        }
    } else {
        c = 0;
        g = m.genre;
        bestList.add(m.id);
    }
}

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

🔑 소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> map = new HashMap();
        ArrayList<Music> musicList = new ArrayList();
        ArrayList<Integer> bestList = new ArrayList();

        for(int i=0 ; i<genres.length ; i++) {
            if(map.containsKey(genres[i])) {
                map.put(genres[i], map.get(genres[i])+plays[i]);
            } else {
                map.put(genres[i], plays[i]);
            }
        }

        for(int i=0 ; i<genres.length ; i++) {
            Music m = new Music(i, map.get(genres[i]), plays[i]);
            musicList.add(m);
        }
        Collections.sort(musicList);

        int c = 0;
        int g = 0;
        Iterator<Music> it = musicList.iterator();
        
        while(it.hasNext()) {
            Music m = it.next();
            c++;
            if(g==m.genre) {
                if(c<2) {
                    bestList.add(m.id);
                }
            } else {
                c = 0;
                g = m.genre;
                bestList.add(m.id);
            }
        }
        
        int[] answer = new int[bestList.size()];
        for(int i=0 ; i<bestList.size() ; i++) {
            answer[i] = bestList.get(i);
        }
        return answer;
    }
}

class Music implements Comparable<Music> {
    int id;
    int genre;
    int play;

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

    @Override
    public int compareTo(Music m) {
        if(this.genre!=m.genre) return m.genre-this.genre;
        else if(this.play!=m.play) return m.play-this.play;
        else return this.id-m.id;
    }
}