[JAVA] 베스트 앨범(코딩테스트 고득점 Kit[해시]) - LEVEL3

문제 설명

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

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

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

제한사항

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

입출력 예

genresplaysreturn

[classic, pop, classic, classic, pop]

[500, 600, 150, 800, 2500]

[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]번 노래를 그다음에 수록합니다.

---

아이디어 및 알고리즘

• 이 문제는 음악의 장르 순위와 그 장르 안에서의 plays수로 1,2등의 고유번호를 찾아서 출력해주는 문제이다. 그래서 먼저 HashMap을 이용해 음악 장르는 Key로 한 음악 장르에 총 plays 수를 Value로 지정했다.
• 그리고 int[] number을 이용해 총 plays 수를 할당하고 sort를 통해 오름차순으로 만들어서 순위를 매길 수 있도록 하였다.
• List<Integer> list 에는 고유번호를 담을 수 있도록 하여 마지막에 answer배열에 넣어주어서 문제 알고리즘을 생각했다.

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
class Solution {
    static HashMap<String, Integer> Hsmap;
    static int[] number;
    static List<Integer> list;
    
     public static int[] solution(String[] genres, int[] plays) {
            Hsmap = new HashMap<String, Integer>();
            int index=0;
            list = new ArrayList<Integer>();
            
            for(int i=0;i<genres.length;i++) {
                if(Hsmap.containsKey(genres[i])) {
                    Hsmap.put(genres[i], Hsmap.get(genres[i])+plays[i]);
                    continue;
                }
                Hsmap.put(genres[i], plays[i]);
            }
            number = new int[Hsmap.size()];
            for(String s : Hsmap.keySet()) {
                number[index++] = Hsmap.get(s);
            }
            Arrays.sort(number); //오름차순
            
            for(int i = index-1;i>=0;i--) {
                String s = findKey(number[i]);
                int max1 = -1;
                int max2 = -2;
                for(int j=0;j<genres.length;j++) {
                    if(!s.equals(genres[j])) continue;
                    if(plays[j] > max1) {
                        max2 = max1;
                        max1 = plays[j];
                    }else if(max1 >= plays[j] && max2 < plays[j]) {
                        max2 = plays[j];
                    }
                }
                int max2check=-1; //반드시 max2는 max1보다 늦게 들어와야한다.
                for(int j=0;j<genres.length;j++) {
                    if(!s.equals(genres[j])) continue;
                    if(plays[j] == max1) {
                        max1 = -1; //같은값이 또 들어오지 못하도록 막기 위해 사용
                        list.add(j);
                    }
                    else if(plays[j] == max2) {
                        max2 = -1;
                        max2check=j;
                    }
                }
                if(max2check >= 0) list.add(max2check);
            }
            int[] answer = new int[list.size()];
            index=0;
            for(int x : list) {
                answer[index++] = x;
            }
            return answer;
        }
     
         public static String findKey(int value) {
             String s= "";
             for(String x : Hsmap.keySet()) {
                 if(Hsmap.get(x) == value) {s=x; break;}
             }
             return s;
         }
    
}

코드 설명

1번째 단계에서는 음악장르에 따른 총 play 수를 저장하고 2단계에서는 number[]로 순위를 매긴 뒤 findKey함수로 HashMap의 value값을 이용해 key값을 반환하도록 하였다. 3단계는 그 반환된 Key(음악 장르)로 순회하면서 MAX1 , MAX2를 찾아내준뒤 list 값에 넣어주었다. 그렇게 장르별 1,2순위의 고유번호를 add 시키고 마지막에 answer 배열에 넣어주어 해결하였다.

 

코드 결과

후일담

HashMap을 늘려서 문제를 풀까 아니면 1개를 이용하여 최대한 이용해볼까 고민하다가 1시간 정도 걸려서 문제를 풀게 되었다. 코드를 보다 약간 무식한 방법이 있어서 그렇게 좋은 코드라 생각하진 않는다. 깔끔하게 했으려면 HashMap을 더 늘렸으면 됐지 않았나 싶기도 하다

그래도 문제가 재밌어서 푸는데 괜찮았다 ㅎㅎ 하루에 4개 포스팅 하려니까 너무 힘들다... 이제부턴 하루에 하나씩만 몰아서 하지 말아야지

( 오늘은 비가 안오고 날씨가 화창해서 기분이가 너무 좋았다! )