베스트 앨범 문제는 프로그래머스 코딩테스트 연습 Hash에 있습니다.
https://programmers.co.kr/learn/courses/30/lessons/42579
저는 개발자 지망생으로 공부하고 있는 대학생입니다.
때문에 아직 많이 부족합니다.
아래의 코드가 해당 문제를 풀 수 있는 코드는 맞지만, 해당 문제를 풀기위한 가장 좋은 코드는 아닙니다.
코드에 문제가 있거나, 부족한 점이 있다면 댓글 달아주시면 감사히 배우겠습니다.
감사합니다.
우선 해당 문제는 노래의 장르(중복 가능)와 play 횟수(중복 가능)를 배열로 주고,
많이 재생된 '노래 장르'의 순서대로,
또, 해당 장르 중에서도 높은 play 횟수를 가진 곡의 번호(index)를 각 최대 2개씩 골라 베스트 앨범에 수록하는 문제입니다.
주어지는 데이터와 return해야하는 값은 아래와 같습니다.
genres | plays | return |
---|---|---|
["classic", "pop", "classic", "classic", "pop"] | [500, 600, 150, 800, 2500] | [4, 1, 3, 0] |
자세한 문제의 내용은 프로그래머스에서 확인하실 수 있습니다.
우선 제 전체 코드입니다.
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
HashMap<String, Integer> totalPlayHashMap = new HashMap<>(); // generes의 값, plays의 값의 합 (genres간의 비교를 위함)
HashMap<Integer, String> indexHashMap = new HashMap<>(); // index를 기반으로 찾는 로직,
ArrayList<Integer> answerArrayList = new ArrayList<>(); // 정답을 저장할 ArrayList
for(int i = 0; i < genres.length; i++){
if (totalPlayHashMap.containsKey(genres[i])) {
// 해당 key를 가진 value가 존재하는 경우, 기존 value에 현재 값을 더한다.
totalPlayHashMap.put(genres[i], totalPlayHashMap.get(genres[i]) + plays[i]);
}
else {
totalPlayHashMap.put(genres[i], plays[i]);
}
// index를 key로 하기 때문에, 중복 확인 불필요
indexHashMap.put(i, genres[i]);
}
// key값을 받아 playHashMap의 value값을 기반으로 내림차순 정렬
String[] sortGenres = totalPlayHashMap.keySet().toArray(new String[0]);
Arrays.sort(sortGenres, new Comparator<String>() {
@Override
public int compare(String key1, String key2) {
return totalPlayHashMap.get(key2) - totalPlayHashMap.get(key1);
}
});
// Genres값을 내림차순 순서대로 찾는다.
for (String key : sortGenres) {
ArrayList<Integer> tempArrayList = new ArrayList<>();
// index를 기반으로 genres와 같은 value값을 찾아 ArrayList에 저장한다.
for (int i = 0; i < genres.length; i++) {
if (key.equals(indexHashMap.get(i))) {
tempArrayList.add(i);
}
}
if(tempArrayList.size() < 2){
// 값이 2개 미만일 때, 정렬 불필요
answerArrayList.add(tempArrayList.get(0));
}
else {
// key를 기준으로 받아온 index를 plays[index]를 기준으로하여 내림차순으로 정렬
Integer[] sortPlays = tempArrayList.toArray(new Integer[0]);
Arrays.sort(sortPlays, new Comparator<Integer>() {
@Override
public int compare(Integer index1, Integer index2) {
return plays[index2] - plays[index1];
}
});
// 2개 이상이기 때문에, 위에서 부터 순서대로 2개 추가
answerArrayList.add(sortPlays[0]);
answerArrayList.add(sortPlays[1]);
}
}
// ArrayList를 int 배열로 변경
int[] answer = answerArrayList.stream().mapToInt(i->i).toArray();
return answer;
}
}
제가 풀이한 방법은 HashMap 2개를 사용하여,
각각 곡 장르에 대한 재생수,
곡 index에 대한 play수를 비교하여 정렬하는 방법을 사용했습니다.
첫번째 HashMap에서는 곡 장르, 총 재생수를 key, value 쌍으로 만들었고,
두번째 HashMap에는 Index , 곡 장르 를 key,value 쌍으로 만들었습니다.
// 곡 장르, 총 재생 수
HashMap<String, Integer> totalPlayHashMap = new HashMap<>();
// index, 곡 장르
HashMap<Integer, String> indexHashMap = new HashMap<>();
// 정답을 저장할 ArrayList
ArrayList<Integer> answerArrayList = new ArrayList<>();
for(int i = 0; i < genres.length; i++){
if (totalPlayHashMap.containsKey(genres[i])) {
// 해당 key를 가진 value가 존재하는 경우, 기존 value에 현재 값을 더한다.
totalPlayHashMap.put(genres[i], totalPlayHashMap.get(genres[i]) + plays[i]);
}
else {
totalPlayHashMap.put(genres[i], plays[i]);
}
// index를 key로 하기 때문에, 중복 확인 불필요
indexHashMap.put(i, genres[i]);
}
이렇게한 이유는, 우선 첫번째 HashMap은 장르별 총 재생수를 구하기 위한 가장 좋은 방법이라고 생각했습니다.
O(n) 즉 한번의 for문으로 곡의 장르마다 몇번의 재생수를 가지는지 쉽게 파악할 수 있었습니다.
// key값을 받아 playHashMap의 value값을 기반으로 내림차순 정렬
String[] sortGenres = totalPlayHashMap.keySet().toArray(new String[0]);
Arrays.sort(sortGenres, new Comparator<String>() {
@Override
public int compare(String key1, String key2) {
return totalPlayHashMap.get(key2) - totalPlayHashMap.get(key1);
}
});
두번째 HashMap은 index를 가지고 있다면,
파라미터로 입력받은 plays에 접근할 수 있기 때문에정렬시 Compare함수를 변경하는 방식으로, 정렬이 가능하다고 생각했습니다.
2중 for문이 들어간 부분이 아쉽습니다. 아마 이부분을 더 효율적으로 수정할 수 있을 것이라고 생각합니다.
// Genres값을 내림차순 순서대로 찾는다.
for (String key : sortGenres) {
ArrayList<Integer> tempArrayList = new ArrayList<>();
// index를 기반으로 genres와 같은 value값을 찾아 ArrayList에 저장한다.
for (int i = 0; i < genres.length; i++) {
if (key.equals(indexHashMap.get(i))) {
tempArrayList.add(i);
}
}
// 값이 2개 미만일 때, 정렬 불필요
if(tempArrayList.size() < 2){
answerArrayList.add(tempArrayList.get(0));
}
else {
// key를 기준으로 받아온 index를 plays[index]를 기준으로하여 내림차순으로 정렬
Integer[] sortPlays = tempArrayList.toArray(new Integer[0]);
Arrays.sort(sortPlays, new Comparator<Integer>() {
@Override
public int compare(Integer index1, Integer index2) {
return plays[index2] - plays[index1];
}
});
// 2개 이상이기 때문에, 위에서 부터 순서대로 2개 추가
answerArrayList.add(sortPlays[0]);
answerArrayList.add(sortPlays[1]);
}
}
// ArrayList를 int 배열로 변경
int[] answer = answerArrayList.stream().mapToInt(i->i).toArray();
return answer;