🤔 문제
🔗
노래의 장르를 나타내는 문자열 배열 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;
}
}