[Java Algorithm] 프로그래머스 Lv.3 _ 베스트앨범

[문제]

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.

 

[Algorithm]

아 이거 너무 어려워서 클로드에게 도움을 청했음

HashMap으로 장르별 총 재생 횟수 구하고 노래 내림차순으로 정렬하는거까지 생각은 했는데 정확히 어떻게 구현해야할지.. 긴가민가..

일단 총 재생 횟수는 앞서 써본 것 처럼 getOrDefault() 사용하고 plays 배열에서 노래를 담는거는 list에 담는거 까지 생각했다.

 

1. 장르별 총 재생 횟수를 구한다.

→ 반복문을 통해 배열의 길이-1만큼 돌면서 HashMap에 각 장르별 재생 횟수를 누적해서 더한다.

2. 각 노래 정보 저장

→ list를 생성해 list에 고유번호와 재생 횟수를 담아준다.

3. 장르별로 노래 그룹화하고 정렬하기

→ HashMap 새로 만든 후, 각 장르별로 객체를 만들고 그 안에 배열로 곡의 고유 번호와 재생 횟수를 담는다.

    이때 곡은 재생 횟수 내림차순으로 정렬해서 담는다. 재생 횟수 같은 경우 고유 번호 오름차순으로 정렬

4. 장르를 재생 횟수 순으로 정렬

→ sort를 활용

5. 장르별로 최대 2개까지만 선택해서 결과 반환

 

 

[Code]

import java.util.*;

class Solution {
   public int[] solution(String[] genres, int[] plays) {
       // 장르별 총 재생 횟수 계산
       Map<String, Integer> genrePlayCount = new HashMap<>();
       for (int i = 0; i < genres.length; i++) {
           genrePlayCount.put(genres[i], genrePlayCount.getOrDefault(genres[i], 0) + plays[i]);
       }
       
       // 장르별 노래 그룹화
       Map<String, List<int[]>> genreSongs = new HashMap<>();
       for (int i = 0; i < genres.length; i++) {
           String genre = genres[i];
           genreSongs.putIfAbsent(genre, new ArrayList<>());
           genreSongs.get(genre).add(new int[]{i, plays[i]});
       }
       
       // 각 장르 내에서 노래 정렬
       for (List<int[]> songs : genreSongs.values()) {
           songs.sort((a, b) -> {
               if (b[1] != a[1]) return b[1] - a[1];  // 재생횟수 내림차순
               return a[0] - b[0];                    // 인덱스 오름차순
           });
       }
       
       // 장르를 총 재생 횟수 순으로 정렬
       List<String> sortedGenres = new ArrayList<>(genrePlayCount.keySet());
       sortedGenres.sort((a, b) -> genrePlayCount.get(b) - genrePlayCount.get(a));
       
       // 결과 생성 (각 장르에서 최대 2개씩)
       List<Integer> result = new ArrayList<>();
       for (String genre : sortedGenres) {
           List<int[]> songs = genreSongs.get(genre);
           for (int i = 0; i < Math.min(2, songs.size()); i++) {
               result.add(songs.get(i)[0]);
           }
       }
       
       return result.stream().mapToInt(i -> i).toArray();
   }
}

 

 

 

[+ 다른 사람 풀이]

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Object> genresMap = new HashMap<String, Object>();      //<장르, 곡 정보> 
        HashMap<String, Integer> playMap = new HashMap<String, Integer>(); //<장르, 총 장르 재생수>
        ArrayList<Integer> resultAL = new ArrayList<Integer>();

        for(int i = 0; i < genres.length; i++){
            String key = genres[i];
            HashMap<Integer, Integer> infoMap;       // 곡 정보 : <곡 고유번호, 재생횟수>

            if(genresMap.containsKey(key)){
                 infoMap = (HashMap<Integer, Integer>)genresMap.get(key);
            }
            else {
                infoMap = new HashMap<Integer, Integer>();
            }

            infoMap.put(i, plays[i]);
            genresMap.put(key, infoMap);

            //재생수
            if(playMap.containsKey(key)){
                playMap.put(key, playMap.get(key) + plays[i]);
            }
            else {
                playMap.put(key, plays[i]);
            }
        }

        int mCnt = 0;
        Iterator it = sortByValue(playMap).iterator();

        while(it.hasNext()){
            String key = (String)it.next();
            Iterator indexIt = sortByValue((HashMap<Integer, Integer>)genresMap.get(key)).iterator();
            int playsCnt = 0;

            while(indexIt.hasNext()){
                resultAL.add((int)indexIt.next());
                mCnt++;
                playsCnt++;
                if(playsCnt > 1) break;
            }
        }

        int[] answer = new int[resultAL.size()];

        for(int i = 0; i < resultAL.size(); i++){
            answer[i] = resultAL.get(i).intValue();
        }

        return answer;
    }

    private ArrayList sortByValue(final Map map){
        ArrayList<Object> keyList = new ArrayList();
        keyList.addAll(map.keySet());

        Collections.sort(keyList, new Comparator(){
            public int compare(Object o1, Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);

                return ((Comparable) v2).compareTo(v1);
            }
        });

        return keyList;
    }
}

 

이 코드는 HashMap을 사용한 또 다른 방식이다.

중첩 HashMap을 사용한 방식인데 genresMap을 {장르명 → HashMap<곡번호, 재생횟수>} 구조로 설계했다.

장르별 총합은 playMap이라는 별도의 HashMap으로 관리했고, 각 곡을 처리할 때마다 해당 장르의 infoMap을 기존 것을 가져오거나 새로 생성해서 genresMap에 저장한다.

이후 장르별 총 재생 횟수 순으로 정렬하고, 각 장르에서 재생횟수가 높은 상위 2곡을 선택하는 방식이다.

정렬은 sortByValue() 유틸리티 함수를 따로 구현해서 Map의 값을 기준으로 내림차순 정렬한 키 목록을 반환하도록 했다.

 

 

 

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
  public class Music implements Comparable<Music>{

    private int played;
    private int id;
    private String genre;

    public Music(String genre, int played, int id) {
      this.genre = genre; 
      this.played = played;
      this.id = id;
    }

    @Override
    public int compareTo(Music other) {
      if(this.played == other.played) return this.id - other.id;
      return other.played - this.played;
    }

    public String getGenre() {return genre;}
  }

  public int[] solution(String[] genres, int[] plays) {
    return IntStream.range(0, genres.length)
    .mapToObj(i -> new Music(genres[i], plays[i], i))
    .collect(Collectors.groupingBy(Music::getGenre))
    .entrySet().stream()
    .sorted((a, b) -> sum(b.getValue()) - sum(a.getValue()))
    .flatMap(x->x.getValue().stream().sorted().limit(2))
    .mapToInt(x->x.id).toArray();
  }

  private int sum(List<Music> value) {
    int answer = 0;
    for (Music music : value) {
      answer+=music.played;
    }
    return answer;
  }
}

 

Stream을 활용한 풀이 방식

속도는 안나와서 효율성 부분에서 많이 떨어지는 코드지만 Stream을 공부하기에는 좋다는 댓글들이 많다 ..

이건 여기 적어두고 나중에 다시 공부해봐야겠다 -

 

[+ Plus]

💡 Map 클래스의 putIfAbsent()

map.putIfAbsent(key, value)

map에 key가 없으면 데이터 셋을 넣고, key가 있으면 null 반환

 

💡Comparator 함수

compare(a, b) 결과

- 음수 : a가 b보다 앞에 위치 (a < b)

- 0 : a와 b는 같은 위치 (a == b)

- 양수 : b가 a보다 앞에 위치 (a > b)

오름차순 정렬 → a - b

내림차순 정렬 → b - a

이 Comparator 함수는 Java를 처음 시작할 때부터 많이 배우는데 난 아직도 익숙하지가 않다..

 

어려워서 검색의 도움을 받았지만 공부가 많이 됐다 ..