프로그래머스(베스트앨범)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

문제설명

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

pop이 더 인기가 많았으므로 pop부터 실린다. 단,  실행한 곡이 많은 순으로 실려야 하므로 4, 1 순서이다.

그 다음 classic은 순서가 3, 0, 2이지만 2곡만 실려야한다 했으므로 3, 0이 실려야한다. 그래서 {4, 1, 3, 0)이 정답이다!!

 

 

문제에 대한 아이디어

• Map에 장르와 재생된 수를 key와 value 값으로 저장한다. 이 때, 같은 장르가 나오면 value 값에 계속 더해준다.

• 제일 많이 들은 장르를 선택하기 위해 장르를 value 값을 기준으로 내림차순으로 선택한다.

• 제일 많이 들은 장르 부터 주어진 장르 배열과 비교하면서 같으면 temp arrayList에 {genre, 재생수, index}를 추가한다. 그 후 재생수를 기준으로 내림차순으로 정렬한다. 그 후 앞에서 부터 2개를 정답 배열에 추가한다.

 

구현

• 각 장르당 몇곡인지 매칭

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> hm = new HashMap<>();
        for(int i = 0; i< genres.length; ++i){
            hm.put(genres[i], hm.getOrDefault(genres[i], 0) + plays[i]);
        }

제일 많은 장르를 선택하기 위해 Map에 매칭하는 과정이다.

자바는 getOrDefault(Key, Default Value) 가 존재한다. 만약 Map에 추가할려는 Key가 존재하면 Key의 value 값을 리턴하고 없으면 default값을 리턴한다. HashMap은 덮어쓰기를 지원하기 때문에 getOrDefault와 자주 같이 쓰인다.

 

• 많이 들은 장르 순으로 정렬하기

ArrayList<String> genreOrder = new ArrayList<>();
for(String key : hm.keySet()){
       genreOrder.add(key);
}
Collections.sort(genreOrder, (o1, o2) -> hm.get(o2) - hm.get(o1));

장르의 순서를 저장할 ArrayList를 하나 만든다. 

자바는 람다식으로 정렬이 가능하다. (o1, o2) -> h.get(o2) - hm.get(o1) 은 내림차순으로 정렬하는 것이다. 

화살표 뒤의 값(return 값)이 양수이면 o1이 더 크다고 생각 그래서 o1을 뒤로 보낸다. 그러므로 o2는 앞으로 온다. 그러면 원래 더큰 o2가 앞으로 왔으므로 내림차순으로 정렬이 된다.  

 

• 정답 찾기

class Music implements Comparable<Music>{
    String genre;
    int play;
    int index;
    public Music(String genre, int play, int index){
        this.genre = genre;
        this.play = play;
        this.index = index;
    }
    
    public int compareTo(Music m){
      return  m.play - this.play;
    }
}

ArrayList<Music> sol = new ArrayList<>(); //정답 ArrayList
for(int j=0; j<genreOrder.size(); ++j){
    ArrayList<Music> temp = new ArrayList<>(); //각 장르당 순서를 구하기 위한 임시 ArrayList
    for(int i =0; i<genres.length; ++i){
         if(genres[i].equals(genreOrder.get(j))){
              temp.add(new Music(genreOrder.get(j), plays[i], i));
         }
    }
    Collections.sort(temp);
    sol.add(temp.get(0)); //무조건 하나는 추가
    if(temp.size() > 1) sol.add(temp.get(1)); // 2개 이상 존재하면 2번째 것도 추가
}

Music이라는 클래스를 만들어서 ArrayList 및 배열로 만든 후 정렬을 할 때 기준을 정할 수 있다.

Comparable<클래스이름>을 implements 하면 된다. 그 후 compareTo를 Override하면 된다.

return 내용은 위에 람다식과 일치한다.

 

• 정답 출력

int[] answer = new int[sol.size()];
for(int i =0; i<sol.size(); ++i){
    answer[i] = sol.get(i).index;
}
return answer;

 

최종 코드

import java.util.*;

class Music implements Comparable<Music>{
    String genre;
    int play;
    int index;
    public Music(String genre, int play, int index){
        this.genre = genre;
        this.play = play;
        this.index = index;
    }
    
    public int compareTo(Music m){
      return  m.play - this.play;
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> hm = new HashMap<>();
        for(int i = 0; i< genres.length; ++i){
            hm.put(genres[i], hm.getOrDefault(genres[i], 0) + plays[i]);
        }
        ArrayList<String> genreOrder = new ArrayList<>();
        for(String key : hm.keySet()){
            genreOrder.add(key);
        }
        Collections.sort(genreOrder, (o1, o2) -> hm.get(o2) - hm.get(o1));
        
        
        ArrayList<Music> sol = new ArrayList<>();
        for(int j=0; j<genreOrder.size(); ++j){
            ArrayList<Music> temp = new ArrayList<>();
            for(int i =0; i<genres.length; ++i){
                if(genres[i].equals(genreOrder.get(j))){
                    temp.add(new Music(genreOrder.get(j), plays[i], i));
                }
            }
            Collections.sort(temp);
            sol.add(temp.get(0));
            if(temp.size() > 1) sol.add(temp.get(1));
        }
        
        int[] answer = new int[sol.size()];
        for(int i =0; i<sol.size(); ++i){
            answer[i] = sol.get(i).index;
        }
        return answer;
    }
}