[프로그래머스] Hash : 베스트 앨범 - L3

1. 문제

 

문제 요약

-  베스트 앨범 수록곡의 고유번호를 차례대로 리턴

-  베스트 앨범 수록 조건

 

     1. 속한 노래가 많이 재생된 장르부터 수록 한다.

     2. 장르 별 가장 많이 들은 2곡을 수록한다. 2곡 미만일 경우 1곡만 수록한다.

 

 

2. 접근

우선 무엇을 해야하는지 생각한다. 크게 2가지가 있다.

 

1. 속한 곡의 재생 수가 많은 순으로 장르 정렬

2. 장르별로 가장 많이 재생된 곡 2개 선정

 

먼저 장르를 어떻게 해시를 이용하여 정렬할 수 있을까 고민했다. 크게 고민된 부분은 장르는 문자열이다 보니 어떤 자료구조를 사용하여 정렬할 지였다. 만약 해시 맵을 이용하여 <장르, 총 재생 수>을 저장하면, 정렬할 때가 문제이다.

 곡들의 총 재생 수인 value만 이용하여 정렬하게 될 텐데, value를 통해서 key를 찾을 수 있어야 한다. 아래와 같은 방법을 사용하면 value를 통해 key를 찾을 수 있다. 하지만 문제 풀 때는 있는지 몰랐다! 그리고 또한 value가 중복일 때, 문제가 발생할 수 있다. 물론 이 문제에서는 장르 마다 재생 곡수가 다르다 명시되어있기 때문에 해당 방법을 써도 되었을 것이다.

 

HashMap : value를 통해 key 찾기

 for(Map.Entry<String, Integer> entry : map.entrySet()){
    if(entry.getValue().equals(26) ){
      keyList.add(entry.getKey());
    }
  }

 

그래서 나는 Genre 클래스를 만들어 장르의 이름과 총 재생 수를 한 쌍으로 관리하고 리스트를 이용하여 저장하기로 했다. 그 후 리스트를 총 재생 수 기준으로 정렬하여 장르들의 순위를 알아낸다. 또한 장르마다 같은 인덱스를 사용해야 하기 때문에 추가로 <장르, 인덱스> 매핑정보를 저장할 HashMap을 사용하였다.

 

1. 장르 별 순위 구하기

장르에 대한 매핑 정보가 있는지 확인 후, 존재하지 않으면 매핑 맵에  gereCount와 함께 매핑 정보를 추가한다. 그 후 재생 횟수를 추가한다. 

	int genreCount = 0;
        List<Genre> genreList = new ArrayList<>();
        List<Music> musicList = new ArrayList<>(200);
        HashMap<String, Integer> genreMapping = new HashMap();

        // 1. 장르 별 순위 구하기
        for(int i=0; i<genres.length; i++){
            musicList.add( new Music(genres[i], i, plays[i]));
            if(!genreMapping.containsKey(genres[i])){
                genreMapping.put(genres[i], genreCount++);
                
                genreList.add(new Genre(genres[i], 0));
            }
            genreList.get(genreMapping.get(genres[i])).addCount(plays[i]);
        }
        
   }
   
class Genre{
    String name;

    int count;

    public Genre(String name, int count){
        this.name = name;
        this.count = count;
    }

    public void addCount(int add){
        this.count += add;
    }

}

 

장르 탐색이 끝났으면 재생 곡수를 기준으로 내림차순 정렬한다.

 	// genreList는 총 재생 횟수에 따라 내림차순 정렬
        Collections.sort(genreList, (o1, o2) -> Integer.compare(o2.count ,o1.count));

 

 

2. 장르별로 가장 재생 횟수가 많은 곡 2개를 알아낸다.

장르를 내림차순 정렬을 했으니 순서대로 장르에 접근하면서 해당 장르를 가진 곡들을 찾아 리스트에 저장한다. 그리고 리스트를 재생 수를 기준으로 내림차순 정렬 시켜 1개 또는 2개의 정보를 restul에 저장한다.

    // 2. 장르 내 노래 선정
        ArrayList<Music> result = new ArrayList<>();
        for(Genre gern : genreList){
            ArrayList<Music> list = new ArrayList<>();
            for(int i=0; i<genres.length; i++){
                if(genres[i].equals(gern.name)){
                    list.add(new Music(gern.name, plays[i], i));
                }
            }
            Collections.sort(list, (o1, o2) -> o2.value - o1.value); // 내림차순 소팅
            result.add(list.get(0)); 	// 1개는 무조건 수록
            if(list.size()!=1){ 	// 더 수록할 곡이 있으면(==장르 내의 노래가 1개보다 많으면) 수록
                result.add(list.get(1));
            }
        }

 

3. 전체 코드

import java.util.*;
class Solution {
    public static int[] solution(String[] genres, int[] plays) {
        int genreCount = 0;
        List<Genre> genreList = new ArrayList<>();
        List<Music> musicList = new ArrayList<>(200);
        HashMap<String, Integer> genreMapping = new HashMap();

        // 1. 장르 별 순위 구하기
        for(int i=0; i<genres.length; i++){
            musicList.add( new Music(genres[i], i, plays[i]));
            if(!genreMapping.containsKey(genres[i])){
                genreMapping.put(genres[i], genreCount);
                genreList.add(new Genre(genres[i], 0));
                genreCount++;
            }
            genreList.get(genreMapping.get(genres[i])).addCount(plays[i]);
        }

        // genreList는 총 재생 횟수에 따라 내림차순 정렬
        Collections.sort(genreList, (o1, o2) -> Integer.compare(o2.count ,o1.count));
        

        // 2. 장르 내 노래 선정
        ArrayList<Music> result = new ArrayList<>();
        for(Genre gern : genreList){
            ArrayList<Music> list = new ArrayList<>();
            for(int i=0; i<genres.length; i++){
                if(genres[i].equals(gern.name)){
                    list.add(new Music(gern.name, plays[i], i));
                }
            }
            Collections.sort(list, (o1, o2) -> o2.value - o1.value); // 내림차순 소팅
            result.add(list.get(0));    // 1개는 무조건 수록
            if(list.size()!=1){     // 더 수록할 곡이 있으면(==장르 내의 노래가 1개보다 많으면) 수록
                result.add(list.get(1));
            }
        }

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

    }

}
class Music{
    String genre;
    int index;
    int value;

    public Music(String genre, int index, int value){
        this.genre = genre;
        this.index = index;
        this.value = value;
    }
}

class Genre{
    String name;

    int count;

    public Genre(String name, int count){
        this.name = name;
        this.count = count;
    }

    public void addCount(int add){
        this.count += add;
    }

}

 

4.  알게 된 점

IntelliJ는 자동완성 되어서 정렬 기준을 바꿀 때 크게 어려움이 없었는데 프로그래머스에서 아무것도 없이 하려니 기억이 안났다. 

정리 해보겠다!

 

Arrays.sort()

• 배열을 정렬하는데 사용
• 기본 데이터 타입 배열, 객체 배열 모두에 사용 가능
• 주어진 배열 직접 변경

 

Collections.sort()

• 컬렉션을 정렬하는 데 사용 한다. ('List', 'Set' 등)
• 주어진 컬렉션을 직접 변경

둘 다 Comparable 인터페이스나 Comparator 인터페이스 중 하나를 구현하고 있어야 한다. 

 

Comparable 인터페이스

• 객체가 자연스러운 순서를 갖도록 하는 것이 목표
• 객체 자체가 비교 로직을 구현
• `compareTo` 메소드 제공해야함
  • 메소드는 현재 객체가 다른 객체보다 작으먄 음수, 같은 0, 크면 양수를 반환해야 함

List<Person> people = new ArrayList<>();
// ... (people에 객체 추가)

Collections.sort(people); // Comparable을 사용하여 정렬



public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // ... (생성자, 다른 메소드 등)

    @Override
    public int compareTo(Person otherPerson) {
        // 비교 로직을 구현하여 자연스러운 순서 정의
        return this.age - otherPerson.age;
    }
}

 

 

Compartor 인터페이스

• 객체의 정렬 순서를 변경하거나 특정 비교 기준 제공하는 것이 목표
• 외부에서 객체들의 정렬 순서를 제어하고자 할 때 사용
• Comparator 인터페이스를 구현한 별도의 클래스를 생성하여 제공
• compare 메소드를 구현 - 반환값에 따라 순서 결정
  • 반환 값이 양수이면 첫 번째 객체(`o1`)이 두 번째 객체(`o2`)보다 크다고 판단 
  • o1.value - o2.value => 오름차순 정렬
  • o2.value - o1.value => 내림차순 정렬

List<Person> people = new ArrayList<>();
// ... (people에 객체 추가)

AgeComparator ageComparator = new AgeComparator();
Collections.sort(people, ageComparator); // Comparator를 사용하여 정렬
Collections.sort(list, (o1, o2) -> o2.value - o1.value); // 내림차순 정렬


public class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person person1, Person person2) {
        // 비교 로직을 구현하여 나이를 기준으로 정렬
        return person1.getAge() - person2.getAge();
    }
}