4. 베스트앨범 (프로그래머스, 해시 Level 4)

* 문제 설명

 - 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다.

 - 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

  1) 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

  2) 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

  3) 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

 - 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때,

 - 베스트 앨범 에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

 

* 제한사항

 - genres[i]는 고유번호가 i인 노래의 장르입니다.

 - plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.

 - genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.

 - 장르 종류는 100개 미만입니다.

 - 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.

 - 모든 장르는 재생된 횟수가 다릅니다.

 

* 결과 예시

genres	plays	return
[classic, pop, classic, classic, pop]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

 

역시나 문제를 이해하는 데 시간이 오래 걸렸습니다.

왜 결과에서 2번배열의 인덱스 값이 없는지 햇갈렸는데..문제속에서 두 개씩 모아라는 문구를 잘못보고 해맸던 것 같습니다.

 

먼저 문제의 카테고리가 "해시"이므로 역시 key와 value의 형태로 값을 정리하였습니다.

public static int[] solution(String[] genres, int[] plays) {
    int[] answer = {};
    HashMap<String, HashMap<Object, Integer>> item = new HashMap<>();
    for(int i=0; i < genres.length ;i++){
        if(item.get(genres[i]) != null){
            HashMap<Object, Integer> mini = item.get(genres[i]);
            mini.put("sum", mini.get("sum")+plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        } else {
            HashMap<Object, Integer> mini = new HashMap<>();
            mini.put("sum", plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        }
    }
    System.out.println(item);
    return null;
}

 

일단 저번과 했던 패턴과 비슷하게 정리를 하여 보았습니다.

key값에는 genres 배열의 문자열을 넣어주었습니다. (장르명칭을 넣었습니다)

그리고 데이터에는 다시 HashMap을 활용하여, 데이터의 인덱스를 key 값으로 인덱스에 해당되는 데이터를 value로 넣었습니다.

또한, sum이라는 값에는 저장된 데이터의 총 합이 들어가게 하였습니다. (재생횟수의 총 합)

해당 내용을 출력하여 보면 아래 사진처럼 결과가 나옵니다.

키값 sum에는 각 데이터의 총 합이, 나머지 키 값은 인덱스로 하였습니다.

 

이제 남은 것은 Map객체에 대한 정렬입니다.

Map객체로 정렬하려면 Java 8에서 제공하는 stream 객체를 활용하면 쉽게 할 수 있습니다.

sum 기준(재생된 횟수의 합)으로 먼저 데이터를 정렬합니다.

public static int[] solution(String[] genres, int[] plays) {
    int[] answer = {};
    HashMap<String, HashMap<Object, Integer>> item = new HashMap<>();
    for(int i=0; i < genres.length ;i++){
        if(item.get(genres[i]) != null){
            HashMap<Object, Integer> mini = item.get(genres[i]);
            mini.put("sum", mini.get("sum")+plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        } else {
            HashMap<Object, Integer> mini = new HashMap<>();
            mini.put("sum", plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        }
    }
    
    final Comparator<Integer> revers = Comparator.reverseOrder();  //오름차순 정렬
    Comparator<Map.Entry<String, HashMap<Object, Integer>>> order = Map.Entry.comparingByValue(
        Comparator.comparing( arg-> arg.get("sum"), revers)
    );  //정렬를 위한 식
    item.entrySet().stream()  //스트림 객체를 가져와
        .sorted(order)  //정렬하여 줍니다.
        .collect(  //collect함수를 호출하여 데이터를 재 조립하여 줍니다.
            Collectors.toMap(
                Map.Entry::getKey, 
                Map.Entry::getValue, (val1, val2) -> val1, 
                LinkedHashMap::new
            )
        )
        .forEach( (key, value)->{
            System.out.println(key + " : "+ value);
        });
    return null;
}

 

좀 복잡한 함수로된 부분들이 존재합니다.

위 내용처럼 stream 객체를 활용하면 위 내용처럼 데이터를 간단하게 정렬할 수 있습니다.

* 참고 : lts0606.tistory.com/358

sum 키값을 중심으로 Map객체가 정렬되었습니다.

 

다음으로 이제 데이터를 가져오는일만 남았습니다.

데이터는 key 값이 배열의 인덱스이며, value는 데이터의 크기(재생된 횟수) 입니다.

위 내용과 비슷하게 데이터를 정렬하여 줍니다. 그리고 여기서 재생곡 갯수가 최대 2개라고 하였으므로 제한(limit)을 2개로 하여 줍니다.

public static int[] solution(String[] genres, int[] plays) {
    int[] answer = {};
    HashMap<String, HashMap<Object, Integer>> item = new HashMap<>();
    for(int i=0; i < genres.length ;i++){
        if(item.get(genres[i]) != null){
            HashMap<Object, Integer> mini = item.get(genres[i]);
            mini.put("sum", mini.get("sum")+plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        } else {
            HashMap<Object, Integer> mini = new HashMap<>();
            mini.put("sum", plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        }
    }
    
    ArrayList<Integer> list = new ArrayList<>();  //데이터를 담을 변수 입니다.
    
    final Comparator<Integer> revers = Comparator.reverseOrder();  //오름차순 정렬
    Comparator<Map.Entry<String, HashMap<Object, Integer>>> order = Map.Entry.comparingByValue(
        Comparator.comparing( arg-> arg.get("sum"), revers)
    );  //정렬를 위한 식
    item.entrySet().stream()  //스트림 객체를 가져와
        .sorted(order)  //정렬하여 줍니다.
        .collect(  //collect함수를 호출하여 데이터를 재 조립하여 줍니다.
            Collectors.toMap(
                Map.Entry::getKey, 
                Map.Entry::getValue, (val1, val2) -> val1, 
                LinkedHashMap::new
            )
        )
        .forEach( (key, value)->{
            value.remove("sum");  //value는 총 합입니다. 총합은 이제 필요 없습니다.
            value.entrySet().stream() //스트림을 열어서,
            .sorted(Map.Entry.comparingByValue(revers))  //값을 기준으로 정렬합니다.
            .collect(
                Collectors.toMap(  //데이터를 재 조립합니다.
                    Map.Entry::getKey, 
                    Map.Entry::getValue, 
                    (oldValue, newValue) -> oldValue, LinkedHashMap::new
                )
            )
            .entrySet().stream()  //마지막으로 스트림을 다시 열어 
            .limit(2)  //최대 2개만 나오도록 변경하고,
            .forEach( arg->{
                list.add((Integer) arg.getKey());  //데이터를 담을 변수에 인덱스를 넣어줍니다.
            });
        });
    return null;
}

 

거의 다 왔습니다. ArrayList<Integer> list라는 변수를 추가하였습니다.

해당 변수는 결과 배열값에 추가하기 위한 대상 입니다.

정렬된 데이터에서 다시 값을 기준으로 정렬하였습니다.

그리고 정렬을 하면서 limit를 부여하여 기준값인 2개만 나오도록 하였습니다.

이제 남은 것은 최종모습으로 탄생한 list 변수에 담긴 데이터를 결과형태로 바꾸는 것 입니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {


public static int[] solution(String[] genres, int[] plays) {
    int[] answer = {};
    HashMap<String, HashMap<Object, Integer>> item = new HashMap<>();
    for(int i=0; i < genres.length ;i++){
        if(item.get(genres[i]) != null){
            HashMap<Object, Integer> mini = item.get(genres[i]);
            mini.put("sum", mini.get("sum")+plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        } else {
            HashMap<Object, Integer> mini = new HashMap<>();
            mini.put("sum", plays[i]);
            mini.put(i, plays[i]);
            item.put(genres[i], mini);	
        }
    }
    
    ArrayList<Integer> list = new ArrayList<>();  //데이터를 담을 변수 입니다.
    
    final Comparator<Integer> revers = Comparator.reverseOrder();  //오름차순 정렬
    Comparator<Map.Entry<String, HashMap<Object, Integer>>> order = Map.Entry.comparingByValue(
        Comparator.comparing( arg-> arg.get("sum"), revers)
    );  //정렬를 위한 식
    item.entrySet().stream()  //스트림 객체를 가져와
        .sorted(order)  //정렬하여 줍니다.
        .collect(  //collect함수를 호출하여 데이터를 재 조립하여 줍니다.
            Collectors.toMap(
                Map.Entry::getKey, 
                Map.Entry::getValue, (val1, val2) -> val1, 
                LinkedHashMap::new
            )
        )
        .forEach( (key, value)->{
            value.remove("sum");  //value는 총 합입니다. 총합은 이제 필요 없습니다.
            value.entrySet().stream() //스트림을 열어서,
            .sorted(Map.Entry.comparingByValue(revers))  //값을 기준으로 정렬합니다.
            .collect(
                Collectors.toMap(  //데이터를 재 조립합니다.
                    Map.Entry::getKey, 
                    Map.Entry::getValue, 
                    (oldValue, newValue) -> oldValue, LinkedHashMap::new
                )
            )
            .entrySet().stream()  //마지막으로 스트림을 다시 열어 
            .limit(2)  //최대 2개만 나오도록 변경하고,
            .forEach( arg->{
                list.add((Integer) arg.getKey());  //데이터를 담을 변수에 인덱스를 넣어줍니다.
            });
        });
    answer = list.stream().mapToInt( i -> i).toArray();      //결과!  
    return answer;
}



}

 

이제 해당내용을 바탕으로 결과를 제출 합니다.

통과하였습니다!

 

기능을 만드는데 다소 어렵지는 않았던 것 같습니다.

그런데 만약 Java 8에서 제공하는 stream을 활용하지 않고 하였더라면 아마도 상당한 시간동안 해매지 않았을 까 합니다.

드디어 해시 부분의 테스트를 전부 완료하였습니다!

다음번에는 스택/큐 문제에 도전하여 보겠습니다.