[프로그래머스] Hash(해시) - 베스트앨범 (Java)

프로그래머스 코딩테스트 연습 - 해시(Hash) : 베스트앨범(https://programmers.co.kr/learn/courses/30/lessons/42579) 

프로그래머스

복잡하고 어렵네요. 저는 머리가 나쁘기 때문에 이 문제를 보자마자 한번에 풀 수가 없습니다. 이 문제를 풀기전에 무작정 코드를 작성해보는 것이 아니라 겸허한 자세로 노트에다가 적으면서 어떻게 문제를 해결할 것인지 구상을 하는 것이 저에게는 좋았습니다. 이 문제는 특이하게 genres 배열의 index가 개별 음악의 고유번호로 설정했습니다. 저는 그래서 더 헷갈렸던 것 같아요. 여기서 문제를 풀기 위한 핵심 키워드는 네 개입니다.

 

해당 음악의 장르, 개별음악의 고유번호, 개별음악의 플레이 횟수, 장르별 총 플레이 횟수

 

이 네 개의 키워드가 이 문제를 조리하기 위한 핵심 재료라고 할 수 있습니다. 그럼 어떻게 조리를 할 것인지 요리계획(?)을 세워봅시다.

 

 

 

 첫번째로 어떤 구조체를 사용할 것인가 입니다.

 

프로그래머스의 연습문제는 문제의 카테고리가 이미 주어져있어서 어떤 방식으로 풀어야 할지에 대한 힌트를 얻고 시작합니다. 하지만 실제 코딩테스트에서는 아무런 힌트가 제시되지 않고 문제만 딸랑 주어지기 때문에 왜? 이런 방식으로 풀어야 하는지에 대해 나름의 인사이트를 가지고 있어야 한다고 생각합니다. 여기서 핵심은 장르별 가장 많이 재생된 top 2 음악을 대상으로 앨범에 수록한다는 것입니다.

 

장르별로 핵심 기준을 문제에서 제시했는데 이를 Key 값으로 사용해서 문제를 해결해볼까 하는 생각이 들었습니다. 이 문제의 코딩은 여기서 시작합니다. 장르별로 Key을 나누어 생각해본다면 HashMap구조가 자연스럽게 떠오르겠죠? 그래서 HashMap을 이용해 구조체를 짜기 시작했습니다.

 

 

 두번째, 그럼 Map의 Value는 무엇으로 집어 넣을 것인가.

 

HashMap을 사용하기로 결정했으면 Key값은 장르가 될 것이고 Value는 어떤 것으로 정해야 할 것인가 정해야 합니다. 처음에 저는 개별 음악의 고유번호와 개별음악의 플레이 횟수, 두 개의 정보가 필요하기에 고유번호와 해당하는 플레이횟수를 Map으로 이용해 Value에 집어넣으면 어떨까 생각했습니다. 그런데 중요한 것은 플레이 횟수가 같은 같은 장르의 음악이 여러개 있을 수 있다는 중복의 문제를 고려해야 합니다. 만약 이러한 경우가 발생하면 문제에서는 고유번호가 더 낮은 것을 높은 우선순위로 두어 앨범에 넣을 것을 요구합니다. 

 

저는 고유번호를 key값으로 하면 중복된 value 값이 존재할 수 있기에 같은 value끼리 묶어서 해당 key값을 오름차순으로 정렬해 상위 2개만 뽑는 그 과정을 생각해보니 제 머리로는 감당이 안되더라구요. 그래서 반대로 생각했습니다.

 

key값을 플레이 횟수로 하고 그에 해당하는 value를 고유번호 리스트로 두었습니다. 이렇게 하면 어차피 맨 처음에 주어진 데이터를 HashMap에 저장할 때 같은 플레이 횟수의 음악들은 고유번호가 낮은 것이 먼저 value리스트에 들어갈 것이기에 알아서 정렬이 된다고 생각하여 이런방식으로 풀었습니다.

 

정리하자면 

 

전체 구조도 : HashMap<장르, 장르에 해당하는 데이터> 

장르에 해당하는 데이터 : HashMap<플레이횟수, 플레이횟수에 해당하는 음악의 고유번호리스트>

플레이횟수에 해당하는 음악의 고유번호리스트 : ArrayList<고유번호(Integer)>

 

이런식으로 구상했습니다.

 

 

 마지막 고려해야할 사항이 또 있는가?

 

전체적인 구조를 짰으니 고려해야 할 사항들을 생각해보아야 합니다.

 

1) 여기서 장르별로 플레이 횟수가 높은 2개의 음악을 뽑느데 장르별로 나눌 때에도 장르별 총 플레이 횟수가 높은 순으로 거기에 해당하는 음악들을 먼저 앨범에 수록한다는 것입니다. 그래서 따로 HashMap을 또 만들어서 Key: 장르, Value: 총 플레이 횟수 이런 식의 구조를 가지고 접근했습니다.

 

여기서 총 플레이 횟수를 기준으로 내림차순해야하는데 HashMap의 Value값을 기준으로 정렬하는 방법을 이용해야 합니다. 제가 참고한 블로그 게시물을 아래에 태그해두었습니다.

 

- HashMap의 Value를 기준으로 한 정렬

// 오름차순
System.out.println("------value 오름차순------");
Collections.sort(keySetList, (o1, o2) -> (map.get(o1).compareTo(map.get(o2))));
        
for(Integer key : keySetList) {
    System.out.println("key : " + key + " / " + "value : " + map.get(key));
}
        
System.out.println();
        
// 내림차순
System.out.println("------value 내림차순------");
Collections.sort(keySetList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));
for(Integer key : keySetList) {
    System.out.println("key : " + key + " / " + "value : " + map.get(key));
}

Lambda를 사용해서 keySetList를 정렬하는 것을 알 수 있습니다. keySetList는 HashMap의 keySet을 ArrayList로 만든 것입니다. 

 

 

2) 또한 고려해야 할 사항이 장르별 개별 플레이 횟수가 높은 2개의 음악을 선택해야 한다는 것입니다. 위에서 HashMap으로 구성한 장르에 해당하는 데이터를 가지고 접근해야 합니다. 여기에 key값은 개별 음악의 플레이 횟수, value는 그에 해당하는 고유번호리스트 입니다. 즉 key값을 기준으로 내림차순 정렬해서 그에 해당하는 고유번호를 value에서 찾아 2개를 뽑아내면 됩니다. 여기서는 HashMap의 key를 기준으로 한 정렬하는 방법을 적용해야 합니다. 이 또한 링크를 아래 걸어두었습니다.

 

- HashMap의 Value를 기준으로 한 정렬

TreeMap<string,string> tm = new TreeMap<string,string>(ht);
Set<string> keyset = ht.keySet();
Iterator<string> keyiterator = tm.keySet( ).iterator( );   //키값 오름차순 정렬
//Iterator<string> keyiterator = tm.descendingKeySet().iterator(); //키값 내림차순 정렬

TreeMap을 사용한 것을 알 수 있습니다. TreeMap은 key값을 기준으로 정렬을 해줍니다. 이를 이용해 플레이 횟수를 내림차순으로 정렬할 수 있습니다.

 

 

import java.util.*;
 
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        
        // 문제의 키워드: 장르, 개별음악의 고유번호, 개별음악의 플레이횟수
        // key: 장르, value: (key: 플레이횟수, value: 고유번호리스트) 
        // 이중 HashMap 구조로 문제풀이
        HashMap<String, 
        HashMap<Integer, ArrayList<Integer>>
            > genreMap = new HashMap<>();
        
        HashMap<Integer, ArrayList<Integer>> playNumMap = null;
        ArrayList<Integer> musicNumberList = null;
        for(int i = 0; i < genres.length; i++){
            // genreMap안에 넣으려는 장르가 새로운 key값인 경우
            if(!genreMap.containsKey(genres[i])){
                playNumMap = new HashMap<>();
                musicNumberList = new ArrayList<>(); 
            } else{ // 넣으려는 장르가 기존에 존재하는 경우
                playNumMap = genreMap.get(genres[i]);
                if(playNumMap.containsKey(plays[i])){
                    musicNumberList = playNumMap.get(plays[i]);    
                } else {
                    musicNumberList = new ArrayList<>();
                }
            }
            musicNumberList.add(i);
            playNumMap.put(plays[i], musicNumberList);
            genreMap.put(genres[i], playNumMap);
        }
        
        // Total plays according to Genres
        // 각 장르별 총 플레이 횟수에 대한 정보
        HashMap<String, Integer> totalPlays = new HashMap<>();
        Iterator<String> keyIter = genreMap.keySet().iterator();
        
        String key = null;
        Integer keyInner = null;
        int total = 0;
        while(keyIter.hasNext()){
            key = keyIter.next();
            playNumMap = genreMap.get(key);
            
            Iterator<Integer> innerIter = playNumMap.keySet().iterator();
            while(innerIter.hasNext()){
                keyInner = innerIter.next();
                total += keyInner * playNumMap.get(keyInner).size();
            }
            totalPlays.put(key, total);
            total = 0;
        }
        
        // Descending Sort by totalPlays' value 
        // 총 플레이 횟수를 기준으로 내림차순
        List<String> sortList = new ArrayList<>(totalPlays.keySet());
        Collections.sort(
            sortList,
            (key1, key2) -> (totalPlays.get(key2).compareTo(totalPlays.get(key1)))
        );
        
        // Select top 2 music according to Genres 
        // 각 장르별로 플레이횟수 상위2개의 음악을 뽑는 과정
        ArrayList<Integer> albumList = new ArrayList<>();
        int count = 0;
        for(String genre : sortList){
            TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<>(genreMap.get(genre));
            Iterator<Integer> tempKey = tm.descendingKeySet().iterator();
            
            while(tempKey.hasNext() && count < 2){
                int playsKey = tempKey.next();
                for(int index = 0; index < tm.get(playsKey).size(); index++){
                    if(count == 2) break;
                    albumList.add(tm.get(playsKey).get(index));
                    count++;
                }
            }
            count = 0;
        }
        
        // 정답지에 해당 ArrayList 정보를 집어넣는 과정
        answer = new int[albumList.size()];
        for(int i = 0; i < answer.length; i++){
            answer[i] = albumList.get(i);
        }
        
        return answer;
    }
}

 

 

 

출처

- HashMap의 key값을 기준으로 정렬 : https://seongsillvanas.tistory.com/7

- HashMap의 value값을 기준으로 정렬 : https://daily-life-of-bsh.tistory.com/99

- TreeMap의 특징에 대한 설명 : https://onsil-thegreenhouse.github.io/programming/java/2018/02/22/java_tutorial_1-24/