베스트 앨범 문제는 프로그래머스 코딩테스트 연습 Hash에 있습니다.
https://programmers.co.kr/learn/courses/30/lessons/42579


저는 개발자 지망생으로 공부하고 있는 대학생입니다.
때문에 아직 많이 부족합니다.

아래의 코드가 해당 문제를 풀 수 있는 코드는 맞지만, 해당 문제를 풀기위한 가장 좋은 코드는 아닙니다.
코드에 문제가 있거나, 부족한 점이 있다면 댓글 달아주시면 감사히 배우겠습니다.
감사합니다.


베스트 앨범 문제

우선 해당 문제는 노래의 장르(중복 가능)와 play 횟수(중복 가능)를 배열로 주고,
많이 재생된 '노래 장르'의 순서대로,
또, 해당 장르 중에서도 높은 play 횟수를 가진 곡의 번호(index)를 각 최대 2개씩 골라 베스트 앨범에 수록하는 문제입니다.


즉 아래의 규칙을 만족하는 베스트 앨범에 수록할 노래를 찾아 순서대로 배열에 담아 return하는 것입니다.

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

주어지는 데이터와 return해야하는 값은 아래와 같습니다.

genresplaysreturn
["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수를 비교하여 정렬하는 방법을 사용했습니다.


1. HashMap을 만들고 해당 HashMap에 데이터를 넣는 부분입니다.

첫번째 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]);
}

2. 총 재생수를 기반으로 첫번째 HashMap의 key(곡 장르)를 배열에 저장후, 정렬하는 부분입니다.

이렇게한 이유는, 우선 첫번째 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);
    }
});

3. 각 곡별 재생수를 기반으로 두번째 HashMap의 key(Index)를 배열에 저장후, 정렬하는 부분입니다.

두번째 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]);
	}
}

4. 마지막으로 ArrayList를 int 배열로 변경하는 부분입니다.

 // ArrayList를 int 배열로 변경
 int[] answer = answerArrayList.stream().mapToInt(i->i).toArray();
 return  answer;
        
profile
Computer System을 공부하는 대학원생 입니다.

0개의 댓글