[프로그래머스] 베스트앨범 JAVA, JavaScript
오랜만에 알고리즘을 한번 풀어봤다. 그래도 나름 자바스크립트로 6개월을 넘게 개발했다고, 자바는 많이 잊어버렸다. 자바스크립트로는 금방 풀이를 떠올릴 수 있었는데, 타입의 제한 때문인지 자바로는 풀기 어려웠다.
먼저 문제를 읽고, 이 문제를 풀기 위해 필요한 값을 정리해봤다.
- 장르별 총 곡 재생 수
- 장르 내에서 가장 많이 재생된 2개 곡의 인덱스 값 (장르 내의 곡이 1개일 경우 1개)
{장르}
:{장르의 총 재생 수}
로 매칭하여 계산하기 편하기 때문에, Hash 카테고리로 분류된 것 같다. 그런데 단순히 장르의 총 재생 수만 필요한 것이 아니라, 그 안에서 가장 많이 재생된 2개 곡의 인덱스도 필요하다.
그래서 저장할 Value를 원시 타입으로 저장하는 것이 아니라, {장르의 총 재생 수, 해당 장르에서 재생된 곡 인덱스/재생 수}
의 형태로 새로운 클래스를 만들어서 저장해보기로 했다.
풀이
위에 설명한 형태를 자바스크립트의 객체 형태로 보자면, 아래와 같이 정보를 저장한다.
genreList = {
classic: {
totalPlay: 1450,
playList: [[0, 500], [2, 150], [3, 800]],
},
pop: {
totalPlay: 3100,
playList: [[1, 600], [4, 2500]],
},
}
이렇게 정리된 정보를 바탕으로 genreList순, genre별 playList의 재생 순으로 정렬한 뒤 값을 가져오면 된다.
사실 효율성을 좋게 개발하려고 하면 이 부분이 제일 난해하다. 일단 장르 정렬을 위해서 한번 전체 순회를 하는데, 이 때 장르 내부도 함께 정렬이 되면 좋겠지만 그 부분까진 방법이 떠오르지 않아서 구현하지 못했다.
장르를 정렬한 다음엔, 장르 내부에서 가장 많이 재생된 순서의 곡 2개를 정렬한다. 장르를 정렬한 것과 동일하게 전체 순회를 돌아서 정렬했다. (하지만 이 부분은 최댓값 2개만 찾으면 되기 때문에 버블 정렬로 두개만 찾아내는 것이 더 나을 것 같다)
코드
JAVA
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.Collections;
import java.util.Comparator;
class Genre {
public int totalPlay;
public List<int[]> playList = new ArrayList<>();
public Genre(int playCount, int[] playList) {
this.totalPlay = playCount;
this.playList.add(playList);
}
public void increaseTotalPlay(int playCount) {
this.totalPlay += playCount;
}
public void addPlayList(int[] playList) {
this.playList.add(playList);
}
}
class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, Genre> genreSummary = new HashMap<>();
for (int i = 0; i < genres.length; i++) {
Genre genre = genreSummary.get(genres[i]);
if (genre == null) {
genreSummary.put(genres[i], new Genre(plays[i], new int[] { i, plays[i] }));
} else {
genre.increaseTotalPlay(plays[i]);
genre.addPlayList(new int[] { i, plays[i] });
}
}
List<Genre> genreList = new ArrayList(genreSummary.values());
Collections.sort(genreList, new Comparator<Genre>() {
public int compare(Genre genre1, Genre genre2) {
return genre2.totalPlay - genre1.totalPlay;
}
});
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < genreList.size(); i++) {
Genre genre = genreList.get(i);
Collections.sort(genre.playList, new Comparator<int[]>() {
public int compare(int[] play1, int[] play2) {
return play2[1] - play1[1];
}
});
answer.add(genre.playList.get(0)[0]);
if (genre.playList.size() > 1) {
answer.add(genre.playList.get(1)[0]);
}
}
return answer.stream().mapToInt(Integer::intValue).toArray();
}
}
JavaScript
function solution(genres, plays) {
const summaryGenres = genres.reduce((acc, cur, index) => {
if (!acc[cur]) {
acc[cur] = {
totalPlay: 0,
playList: [],
};
}
acc[cur].totalPlay += plays[index];
acc[cur].playList.push([index, plays[index]]);
return acc;
}, {});
const summaryGenresList = Object.values(summaryGenres).sort(
(genre1, genre2) => {
return genre2.totalPlay - genre1.totalPlay;
},
);
const answer = summaryGenresList.reduce((acc, genre) => {
genre.playList.sort((play1, play2) => {
return play2[1] - play1[1];
});
acc.push(genre.playList[0][0]);
if (genre.playList.length > 1) {
acc.push(genre.playList[1][0]);
}
return acc;
}, []);
return answer;
}