[프로그래머스 : 레벨 3] 베스트 앨범 : List를 이용한 정렬(Java)

문제

 

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

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]

 

입출력 예 설명

 

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

 

 

문제 해설 : 재생횟수가 제일 많은 2곡을 재생횟수 많은 장르 순부터 모아둔 배열을 return 해라.

 

문제를 자세히 살펴보니 결국엔 입력받는 배열에서의 index가 곡의 고유번호가 된다는걸 알게 됐다.

 

나는 이 개념을 가지고 활용해서 아래와 같은 코드를 짰다.

 

나의 코드

 

import java.util.*;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        int[] answer = {};
        
        //장르별 재생횟수 저장하는 hashMap 생성
        HashMap<String,Integer> hm = new HashMap<>();
        
        //plays에서 index랑 재생횟수 저장하는 HashMap 생성
        HashMap<Integer, Integer> hm2 = new HashMap<>();
        
        //plays 저장
        for(int i = 0;i<plays.length;i++){
            hm2.put(i,plays[i]);
        }
        
        //HashMap에 장르랑 재생횟수를 넣는 부분
        for(int i = 0;i < genres.length ; i++){
            if(hm.containsKey(genres[i])){ //장르가 이미 있다면 진입
                hm.put(genres[i], hm.get(genres[i])+ plays[i] );
            }else{
                hm.put(genres[i],plays[i]);
            }
        }
        
        //장르별로 모아둔걸 정렬하기위햇 List 만듬
        List<String> genreSet = new ArrayList<>(hm.keySet());
        
        //키값으로 저장되어 있는 list에서 o2랑 o1 비교해서 내림차순으로 저장
        Collections.sort(genreSet,(o1,o2) -> (hm.get(o2).compareTo(hm.get(o1))));
        
        //재생횟수랑 index 모아둔거 정렬하기 위해 list 만듬
        List<Integer> indexSet = new ArrayList<>(hm2.keySet());
        
        //내림차순으로 정렬
        Collections.sort(indexSet, (o1,o2)->(hm2.get(o2).compareTo(hm2.get(o1))));
        
        
        
        List<Integer> answerList = new ArrayList<>();
        
        for(String s: genreSet){
            int count = 1;
            for(int i : indexSet){
                if(genres[i].equals(s) && count<3){ //같은 장르이고 베스트 2 이면 진입
                    count++;
                    answerList.add(i);
                }
            }
        }
        
        answer = new int[answerList.size()];
        
        for(int i = 0; i<answer.length;i++){
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
}

 

 

나는 일단 고유번호(index)별 재생횟수를 저장하고 그 다음엔 장르별 재생횟수를 저장했다.

 

장르별 재생횟수를 저장하는 방법은 내가 이전에 사용했던 완주하지 못한 선수와 위장 문제에서 사용했던 방식

Key값이 같으면 value값을 계속해서 더하는 방식을 사용했다.

 

       //plays 저장
        for(int i = 0;i<plays.length;i++){
            hm2.put(i,plays[i]);
        }
        
        System.out.println(hm2);
        
        //HashMap에 장르랑 재생횟수를 넣는 부분
        for(int i = 0;i < genres.length ; i++){
            if(hm.containsKey(genres[i])){ //장르가 이미 있다면 진입
                hm.put(genres[i], hm.get(genres[i])+ plays[i] );
            }else{
                hm.put(genres[i],plays[i]);
            }
        }

 

그래서 저장한 hashMap을 출력해 보면 아래와 같다.

 

	{0=500, 1=600, 2=150, 3=800, 4=2500}
	{pop=3100, classic=1450}

 

나는 이를 문제의 의도 대로 내림차순으로 정렬을 했다.

 

정렬한 방법은 HashMap을 keySet으로 바꿔 List에 담았다.

(List는 순서가 중요하기 때문에 안에서 정렬 메소드를 사용가능하다.)

 

List에 담고 나서는 해당 List를 

Collection.sort()라는 메소드를 사용해서 정렬을 했다.

 

Collection를 사용하려면 이를 상속한 클래스를 구현해야하는데 나는 이를 람다식 표현을 사용해서 익명객체를 만들어 사용했다.

 

       //장르별로 모아둔걸 정렬하기위햇 List 만듬
        List<String> genreSet = new ArrayList<>(hm.keySet());
        
        //키값으로 저장되어 있는 list에서 o2랑 o1 비교해서 내림차순으로 저장
        Collections.sort(genreSet,(o1,o2) -> (hm.get(o2).compareTo(hm.get(o1))));
        
        //재생횟수랑 index 모아둔거 정렬하기 위해 list 만듬
        List<Integer> indexSet = new ArrayList<>(hm2.keySet());
        
        //내림차순으로 정렬
        Collections.sort(indexSet, (o1,o2)->(hm2.get(o2).compareTo(hm2.get(o1))));

Collections.sort 방식을 살펴보자면

사용하는 인자는 List로 만든것을 인자로 넣고

그다음엔 비교대상인 인자 o1,o2를 인자로 받고 

hm2.get(o2).compareTo(hm2.get(o1) 를 return 하는 익명 객체를 사용한다는 뜻이다.

 

이렇게 정렬한 list들을 만들었다 출력해보면 아래와 같다.

 

[pop, classic]
[4, 3, 1, 0, 2]

 

자그럼 이제 거의 다왔다.

위의 장르 내림차순한걸 반복해서 들어가면서

아래 재생횟수 내림차순한 index의 장르가 위의 재생횟수 많은 장르가 같으면 진입하게 하면 된다.

 

        List<Integer> answerList = new ArrayList<>();
        
        for(String s: genreSet){
            int count = 1;
            for(int i : indexSet){
                if(genres[i].equals(s) && count<3){ //같은 장르이고 베스트 2 이면 진입
                    count++;
                    answerList.add(i);
                }
            }
        }

위에 count는 장르별 베스트 2만 담기 위해서 만든것이고

answerList는 answer 배열에 담기위해서 순서대로 담을 list를 만들어 거기에 담게 했다.

 

그리고 마지막으로 answer 배열에 answerList안의 내용들을 집어 넣었다.

       answer = new int[answerList.size()];
        
        for(int i = 0; i<answer.length;i++){
            answer[i] = answerList.get(i);
        }

 

이번걸 풀면서 느낀점

1. 문제를 진짜 자세히 보고 요구사항이 뭔지부터 확인하자

2. HashMap에 Key값와 value 값을 뭘 넣을지 곰곰히 생각해보자.

 

내스스로 푼 문제라서 기분이 너무 좋았다.....