[알고리즘 문제 풀이] 프로그래머스 - 베스트앨범

문제 원본 링크: programmers.co.kr/learn/courses/30/lessons/42579?language=java

카테고리: 해시

 

문제 설명

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

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

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

 

제한 사항

1. genres[i]는 고유번호가 i인 노래의 장르
2. plays[i]는 고유번호가 i인 노래가 재생된 횟수
3. genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하
4. 장르 종류는 100개 미만
5. 장르에 속한 곡이 하나라면, 하나의 곡만 선택
6. 모든 장르는 재생된 횟수가 다름

입출력 예시

String[] genres = {"classic", "pop", "classic", "classic", "pop"};
int[] plays = {500, 600, 150, 800, 2500}; 
// return {4, 1, 3, 0}

 

입출력 예시 설명

classic 장르는 1,450회 재생, classic 노래는 아래와 같음

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 아래와 같음

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop장르의 [4, 1]번 노래를 먼저, classic 장르의 [3,0]번 노래를 그 다음에 수록한다. 

 

---

풀이 과정

1. 먼저 장르별 모든 곡의 재생수 합계를 HashMap<String, Integer> playsOfGenres에 저장한다.
2. 장르별 총 음악수를 HashMap<String, Integer> musicsOfGenres에 저장하여 나중에 장르 안에 담긴 곡이 2개 미만인 경우를 찾는데 사용한다.
3. index를 기준으로하는 재생수를 찾는데 사용하기 위해 HashMap<Integer, Integer> indexOfPlays를 만든다. 
4. 재생수를 기준으로 오름차순 정렬하기 위해 playsOfGenres를 TreeMap<Integer, String> treeMap에 저장한다. => 재생수가 많은 장르별로 우선 탐색하여 index를 저장하기 위함
5. treeMap의 value 값, String genre을 기준으로 반복문을 실행한다.
6. musicsOfGenres.get(genre) 값을 기준으로 장르별 베스트앨범을 두 개를 담을지 한 개를 담을지 결정한다. 
7. genres와 plays를 순서대로 탐색해서 genre와 genres[index]가 일치하면서 가장 큰 값을 찾는다. 
8. 찾은 값의 index를 indexOfBest에서 제거하여 다시 탐색하지 않도록한다. 

우선 장르별 모든 음악의 재생수 합계를 구해야 한다. 그리고 재생수가 큰 순서대로 정렬하면 첫 번째 조건대로 곡을 수록할 수 있다. HashMap을 사용하여 저장한 후에 다시 TreeMap에 저장하면 쉽게 정렬까지 할 수 있다. 

 

HashMap을 총 세 번 만들어서 사용했다. 두 번째는 장르별 총 음악의 개수를 저장해서 <제한사항> 5번의 경우를 예외처리하는 용도로 사용했다. 더 좋은 방법이 있을 것이다. 세 번째 HashMap은 고유번호를 key로 하고, 재생수를 value로 저장해서 재생수가 같은 경우 고유번호가 낮은 노래를 먼저 수록하는 용도로 사용했다. 

 

Java 코드

public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> playsOfGenres = new HashMap<>(); // 장르별 총 재생수
        HashMap<String, Integer> musicsOfGenres = new HashMap<>(); // 장르별 총 음악수
        HashMap<Integer, Integer> indexOfPlays = new HashMap<>(); // index를 key로 하는 재생수

        for (int i = 0; i < genres.length; i++) {
            playsOfGenres.put(genres[i], playsOfGenres.getOrDefault(genres[i], 0) + plays[i]);
            musicsOfGenres.put(genres[i], musicsOfGenres.getOrDefault(genres[i], 0) + 1);
            indexOfPlays.put(i, plays[i]);
        }

        // TreeMap에 저장하면 자동으로 key 기준으로 정렬, reverseOrder 내림차순 정렬
        TreeMap<Integer, String> treeMap = new TreeMap<>(Collections.reverseOrder());
        playsOfGenres.forEach((s, integer) -> treeMap.put(integer, s));

        List<Integer> indexOfBests = new ArrayList<>();
        for (String genre : treeMap.values()) { // 재생수 많은 장르 순서로 반복

            int bestNumbers = musicsOfGenres.get(genre) > 1 ? 2 : 1; // 베스트앨범에 들어갈 장르별 음악수
            for (int i = 0; i < bestNumbers; i++) {

                int index = 0;
                int biggestPlays = 0;
                for (int j = 0; j < genres.length; j++) {
                    // indexOfBest에 들어갈 index찾기
                    if (indexOfPlays.containsKey(j) &&
                            genres[j].equals(genre) &&
                            plays[j] > biggestPlays) {
                        index = j;
                        biggestPlays = plays[j];
                    }
                }
                indexOfPlays.remove(index); // 찾은 인덱스는 map에서 제거해서 다시 입력되지 않도록함
                indexOfBests.add(index);
            }
        }

        return indexOfBests.stream().mapToInt(i -> i).toArray();
    }

 

채점 결과

계산 시간이 어림잡아 평균 5ms정도 나왔다. 괜찮은 수치인지 모르겠다. 그리고 코드도 간결하지 않다. 더 간결하면서 우수한 코드를 작성하는 법이 분명 많이 있을 것이다.

 

다른 사람의 풀이

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;
  }
}

문제 채점 후에 볼 수 있는 다른 사람의 풀이 중 가장 추천을 많이 받은 코드다. solution함수만 보면 stream을 사용해서 상당히 우아하고 간결하다. Music 클래스를 만들어 Comparable을 구현한 점도 흥미롭다. 나는 사실 많이 안써본 방식이지만 배워야겠다. 다만 stream함수를 복잡하게 사용하면 많은 경우 처리시간이 오래걸린다. 위 코드의 경우 내 코드의 처리사간의 3배 정도가 걸린다. 

 

 

참고

- 문제 풀이 소스 코드(깃허브)