[프로그래머스] 베스트 앨범

1. 문제

---

프로그래머스

2. 풀이 과정

---

1. 재생횟수 총합을 기준으로 높은 순으로 장르 정렬하기

 

2. 장르안에서도 재생횟수 많은 노래를 알기 위해 모든 노래에 대해서 재생 횟수 기준으로 정렬 

 

3. 장르 순서를 기반으로 해당 장르의 노래 중 재생횟수가 높은 노래 2개씩 배열에 넣기

 

두 개의 정보를 통해 정답을 구해야한다. 각각의 정보를 뽑아내는 과정은 다음과 같다.

이해를 위해 위의 테스트케이스를 예시로 설명하겠다.

genre:

["classic", "pop", "classic", "classic", "pop"]

play:

[500, 600, 150, 800, 2500]

 

1. 재생횟수 총합을 기준으로 높은 순으로 장르 정렬하기

 

1) 장르 - 재생횟수 총합의 관계를 가지는 해시맵에 정보 저장

2) 재생횟수로 내림차순 정렬 한 뒤 장르를 별도의 배열의 저장

 

2. 장르안에서도 재생횟수 많은 노래를 알기 위해 모든 노래에 대해서 재생 횟수 기준으로 정렬

 

1) Song 클래스 만들기

다음 3가지를 인스턴스로 가진다.

• id: 노래의 고유번호(배열의 인덱스)
• genre: 노래의 장르(genre[]의 원소)
• play_time: 재생횟수(play[]의 원소)

 2) 이 Song클래스 객체 리스트에 저장하기

 3) song의 play_time을 기준으로 내림차순 정렬하기

 

이제 필요한 정보를 가져왔으니 정답만 구하면 된다. 

3. 장르 순서를 기반으로 해당 장르의 노래 중 재생횟수가 높은 노래 2개씩 배열에 넣기

 1) pop

 

 2) classic

 

답: [4, 1, 3, 0]

 

3. 내 코드

---

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Song> song_list = new ArrayList<>();
        HashMap<String, Integer> genre_time = new HashMap<>();
        List<Integer> answer = new ArrayList<>();
        
        // 1. 장르 - 재생횟수 관계로 저장 후 재생횟수로 정렬
        for(int i = 0; i < genres.length; i++) {
            genre_time.put(genres[i], genre_time.getOrDefault(genres[i], 0) + plays[i]);
        }
        
        List<Map.Entry<String, Integer>> list = new ArrayList<>(genre_time.entrySet());
        
        list.sort((e1, e2) -> Integer.compare(e2.getValue(), e1.getValue()));
        
        // 2. 노래를 리스트에 정렬후 재생횟수로 내림차순 정렬
        for(int i = 0; i < genres.length; i++) {
            song_list.add(new Song(i, genres[i], plays[i]));
        }
        
        song_list.sort((s1, s2) -> Integer.compare(s2.getPlayTime(), s1.getPlayTime()));
        
        
        // 3. 1,2의 결과를 가지고 장르 순대로 재생횟수가 높은 노래 2개씩 배열에 넣기
        for(Map.Entry<String, Integer> entry: list) {
            
            int add_cnt = 0;
            for(Song s: song_list) {
                if(s.getGenre().equals(entry.getKey())) {
                    add_cnt++; 
                    answer.add(s.getId());
                }
                if(add_cnt == 2) {
                    break;
                }
            }
        }
        
        return answer.stream().mapToInt(i -> i.intValue()).toArray();
    }
    
    // 노래 클래스
    static class Song {
        int id;
        String genre;
        int play_time;
        
        public Song(int id, String genre, int play_time) {
            this.id = id;
            this.genre = genre;
            this.play_time = play_time;
        }
        
        public int getId() {
            return this.id;
        }
        
        public String getGenre() {
            return this.genre;
        }
        
        public int getPlayTime() {
            return this.play_time;
        }
    }
}

시간 복잡도

• O(NlogN)

 

// 3. 1,2의 결과를 가지고 장르 순대로 재생횟수가 높은 노래 2개씩 배열에 넣기
for(Map.Entry<String, Integer> entry: list) {

    int add_cnt = 0;
    for(Song s: song_list) {
        if(s.getGenre().equals(entry.getKey())) {
            add_cnt++; 
            answer.add(s.getId());
        }
        if(add_cnt == 2) {
            break;
        }
    }
}

언뜻 보면 이 부분이 O(N^2)처럼 보일 수 있다.

하지만 장르의 종류는 100 미만이다.

문제 제한사항 중

그러므로 이는 상수로 고려하고 무시할 수 있다. 

따라서 내 코드의 시간복잡도는 정렬하는 부분에 대한 O(NlogN)이 시간복잡도가 된다.

 

문제의 제한사항을 보고 입력의 크기를 잘 파악한 다음 시간복잡도를 고려해 코드를 작성해야 한다.

4. 피드백

---

• 하나의 데이터 안에 여러 개의 데이터가 존재한다면 클래스를 선언하는 것도 하나의 방법이다.
• 해시 맵을 value를 기준으로 정렬하려면 entrySet() 메서드를 통해 List로 변환한 다음 정렬해야 한다.