[프로그래머스 알고리즘] 3단계 - 카카오 베스트앨범

프로그래머스 3단계 카카오 베스트앨범

 url : https://programmers.co.kr/learn/courses/30/lessons/42579?language=java

문제설명

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

 - 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

 - 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

 - 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

 - 노래의 장르를 나타내는 문자열 배열 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]번 노래를 그다음에 수록합니다.

자바코드

          
package Q0066;

import java.util.*;

public class Solution {

    public static int[] solution(String[] genres, int[] plays) {
        Map
 genreMap = new HashMap<>(); // 고유번호, 장르
        Map playMap = new HashMap<>(); // 고유번호 플레이수
        Map sortedGenreMap = new TreeMap<>(); // 장르 누적플레이수
        for (int i = 0; i < plays.length; i++) {
            genreMap.put(i, genres[i]);
            playMap.put(i, plays[i]);
            sortedGenreMap.put(genres[i],
                    sortedGenreMap.containsKey(genres[i]) ? sortedGenreMap.get(genres[i]) + plays[i] : plays[i]);
        }

        List list = new ArrayList<>();
        sortedGenreMap.keySet().stream()
                .sorted((o1, o2) -> sortedGenreMap.get(o2) - sortedGenreMap.get(o1))
                .forEach(genre -> {
                    genreMap.keySet().stream()
                            .filter(key -> genreMap.get(key).equals(genre))
                            .map(key -> playMap.get(key))
                            .sorted(Collections.reverseOrder())
                            .limit(2)
                            .forEach(value -> {
                                playMap.keySet().stream()
                                        .filter(v -> playMap.get(v).equals(value))
                                        .limit(1)
                                        .forEach(result -> {
                                            list.add(result);
                                            playMap.put(result, -1);
                                        });
                            });
                }
        );
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

코드 설명

Map을 사용하여 문제를 해결하는 것이 포인트이다. 그리고 Map에 키값을 무엇으로 설정하는지가 중요했다. 장르는 중복이 가능하고, 플레이수도 중복이

가능하기 때문에 키값으로 적절하지 않았다. 중복이 허용되지 않는 것은 누적플레이수와 고유번호이다. 조건에 누적플레이수는 중복이 될 수 없다는 조건이 

있지만, 누적 플레이수로는 키들을 식별하기가 어렵기 때문에 부적합하다. 그렇다면 고유번호가 이름 그대로 키값에 적합하다. 

코드를 보면, 람다식을 사용했지만, 엄청난 반복문을 통해 결괄르 얻는다. 정확성만 테스트하고, 속도측면은 테스트를 하지 않아서 이와같이 풀었다.

코드의 순서는 다음과 같다. 

 1. genreMap에는 <고유번호, 장르>, playMap에는 <고유번호, 플레이수> sortedGenreMap에는 <장르, 장르에 대한 누적 플레이수> 를 저장한다.

 2. sortedGenreMap을 스트림과 람다를 이용해서 누적플레이수 내림차순으로 정렬 

 3. sortedGenreMap을 forEach를 이용해서 누적플레이수가 높은 장르 하나(예 : 팝)를 꺼내서, genreMap에서 값이 팝에 해당하는 키(고유번호)만 추출한다. 

 4. 고유번호를 이용해서 playMap에서 플레이수를 최대 2개 꺼낸다. (limit을 사용했기 때문에 만약 1개면 1개만, 2개면 2개, 3개 이상이면 2개 꺼낸다)

 4. 추출한 플레이수를 playMap에서 비교하여 값이 같은 고유번호만 출력한다. (단, limit을 1로 제한 것은 동일한 플레이수가 있기 때문에 제한했다.)

    (그리고 추출한 플레이수는 -1이라는 쓰레기값을 부여해서 해당 고유번호를 다시 접근하지 않도록 설정했다) 

Pain Point

스트림과 람다를 활용했기 때문에 나름 다른 코드에 비해 라인수도 적고, 가독성이 좋은것 같다. (오직 주관적인 나의 생각)

그러나 반복문을 너무 많이 도는 것은 아닌가? 속도 측면에서는 굉장히 문제가 있지 않을까? 라는 생각이 든다.

요즘 스트림과 람다를 공부하고 있는데, 사용할 수록 기능도 많고 편한것 같다!

어제도 알고리즘 필기테스트를 봤는데, 그래도 계속 공부하니까 이전보다 실력이 향상된것 같다. 

그래서 친한 지인에게 "알고리즘이 이전보다 늘지 않았냐?" 라고 물었지만, 돌아오는 대답은 "공부하는데 안 늘면 사람이냐?" 라는 대답이었다.

나중에 만나면 향상된 알고리즘 역량으로 척추뼈를 내림차순으로 재정렬해주어야 겠다. 시간복잡도 최고 높은 O(n^2)으로 정렬해줘야지!