[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]

 

 

 

# 풀이과정 (Map 이용) --> 정확성 2, 15 실패

class Solution {
    public ArrayList solution(String[] genres, int[] plays) {

        Map<String, Integer> genresPriorMap = new HashMap<>();
        Map<Integer, String> map = new TreeMap<>();
        Map<Integer, Integer> playsMap = new TreeMap<>();

        for (int i = 0; i < genres.length; i++) {
            genresPriorMap.put(genres[i], genresPriorMap.getOrDefault(genres[i], 0) + plays[i]);
            map.put(plays[i], genres[i]);
            playsMap.put(plays[i], i);
        }
		
        // 장르 우선순위 결정 위한 정렬
        List<String> sortedGenresPriorMap = new ArrayList<>(genresPriorMap.keySet());
        Collections.sort(sortedGenresPriorMap, (o1, o2) -> (genresPriorMap.get(o2).compareTo(genresPriorMap.get(o1))));

        ArrayList<Integer> answer = new ArrayList<>();
        List<Integer> mapKeySet = new ArrayList<>(map.keySet());
        List<String> mapValueSet = new ArrayList<>(map.values());

        for (String priority : sortedGenresPriorMap) { // 장르 우선순위 선정
            int cnt = 0;
            
            for (int i = map.size() - 1; i >= 0; i--) {
                if (priority.equals(mapValueSet.get(i))) { // 장르 우선순위에 따라 answer 에 추가
                    cnt++;
                    if (cnt <= 2) {
                        answer.add(mapKeySet.get(i));
                    }
                    else {
                        break;
                    }
                }
            }
        }

        for (int i = 0; i < answer.size(); i++) {
            answer.set(i, playsMap.get(answer.get(i)));
        }

        return answer;
    }
}

풀이 방법

    1. sortedGenresPriorMap 우선순위인 장르 선정

    2. mapValueSet 에서 우선순위 곡의 인덱스 서칭

    3. 2 에서 받은 인덱스로 mapKeySet 에서 우선순위에 해당하는 plays 원소 값 answer 에 추가

    4. 3 에서 생성된 plays 원소 값 배열을 playsMap 에서 원소 값에 해당하는 인덱스로 변경

 

 

회고

• 문제설명에서 '장르 내에서 재생 횟수가 같은 노래' 가 있다는 것을 놓침.

s.solution(new String[] {"classic", "pop", "classic", "classic", "Jazz"}, new int[] {500, 5000, 800, 800, 2500})

위 테스트케이스 실행 시 기댓값 {1, 4, 2, 3} 과 달리 결과값 {1, 4, 3, 0} 이 출력됨.

 

 

 

# 풀이과정 (Map 이용) --> 정확성 통과

class Solution {
    public ArrayList solution(String[] genres, int[] plays) {

        Map<String, Integer> genresPriorMap = new HashMap<>(); // 장르 별 plays 합
        Map<Integer, String> map = new TreeMap<>(); // plays 수 별 오름차순으로 정리된 맵
        Map<Integer, Integer> playsMap = new TreeMap<>(); // plays 수 별 인덱싱 된 맵

        for (int i = 0; i < genres.length; i++) {
            genresPriorMap.put(genres[i], genresPriorMap.getOrDefault(genres[i], 0) + plays[i]);
            map.put(plays[i], genres[i]);
            playsMap.put(i, plays[i]);
        }

        // 장르 우선순위 결정 위한 정렬
        List<String> sortedGenresPriorMap = new ArrayList<>(genresPriorMap.keySet());
        Collections.sort(sortedGenresPriorMap, (o1, o2) -> (genresPriorMap.get(o2).compareTo(genresPriorMap.get(o1))));

        ArrayList<Integer> answer = new ArrayList<>(); // 정답
        List<Integer> mapKeySet = new ArrayList<>(map.keySet()); // map 의 key 값만으로 리스트 생성
        List<String> mapValueSet = new ArrayList<>(map.values()); // map 의 value 값만으로 리스트 생성
                                                                  // --> 리스트들의 끝의 인덱스부터 서칭 할 것임. --> TreeMap 으로 오름차순 정렬 되어있기 때문

        /*
        *  1. sortedGenresPriorMap 우선순위인 장르 선정
        *  2. mapValueSet 에서 우선순위 곡의 인덱스 서칭
        *  3. 2 에서 받은 인덱스로 mapKeySet 에서 우선순위에 해당하는 plays 원소 값 서칭
        *  4. 3 에서 받은 plays 원소 값으로 playsMap 에서 인덱스 서칭하여 answer 에 추가
        * */
        for (String priority : sortedGenresPriorMap) { // 장르 우선순위 선정
            int cnt = 1; // 장르 별 최대 두 곡만 수록

            for (int i = map.size() - 1; i >= 0; i--) {
                if (priority.equals(mapValueSet.get(i))) { // 장르 우선순위 선정
                    if (cnt <= 2) {

                        for (Map.Entry<Integer, Integer> entry : playsMap.entrySet()) {
                            if (mapKeySet.get(i).equals(entry.getValue())) { // 우선순위에 해당하는 plays 수 인덱싱 뽑아내기
                                cnt++; // 장르 별 최대 두 곡을 위해 한 곡 수록 시 ++
                                answer.add(entry.getKey());
                            }
                        }
                    }
                    else {
                        break;
                    }
                }
            }
        }

        return answer;
    }
}

풀이 방법

    1. sortedGenresPriorMap 우선순위인 장르 선정
    2. mapValueSet 에서 우선순위 곡의 인덱스 서칭
    3. 2 에서 받은 인덱스로 mapKeySet 에서 우선순위에 해당하는 plays 원소 값 서칭
    4. 3 에서 받은 plays 원소 값으로 playsMap 에서 인덱스 서칭하여 answer 에 추가
        

 

회고

• Map 을 통하여 keySet 메서드 (Key 값 배열 생성), values 메서드 (Value 값 배열 생성) 으로 배열 변환 시 Key 값의 중복이 제거 되었기 때문에 plays[i] 와 인덱싱 되어 있는 Map 을 생성해야 했음.
• 통과는 했지만 Map 3개와 배열 3개 생성으로 코드가 너무 난잡함. 클린 코드가 필요...

 

 

코드 실행 결과

 

 

- Just Do It -