🔗 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42579
🤔 문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
📌 제한 사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다
😮 문제 해결 방법
장르를 키 값으로 가지고 합계를 값으로 넣어주는 totalCount 맵과 똑같이 장르를 키 값으로 가지고 인덱스 값과 해당 인덱스의 곡 재생횟수를 넣어주는 index 맵을 생성했다.
Map<String,Integer> totalCount = new HashMap<>(); // 합계를 넣어줄 Map
Map<String,Map<Integer,Integer>> index = new HashMap<>(); // 인덱스와 값을 넣어줄 Map각각의 맵을 생성하고 totalCount맵은 value값인 합계를 기준으로 내림차순 정렬을 해주고, index 맵 또한, value 값이 (인덱스 숫자,재생횟수)이므로 인덱스 숫자의 value값인 재생횟수로 내림차순 정렬을 해준 후 데이터를 index 맵의 size가 1보다 크면 차례로 앞의 두개를, 1개인 경우 한 개를 뽑아서 해당 인덱스값을 배열에 넣어 배열을 return하면 문제가 해결된다.
//totalCount Map에서 합계를 기준으로 내림차순으로 정렬
Collections.sort(keySet, (o1,o2) -> totalCount.get(o2).compareTo(totalCount.get(o1)));
//index Map에서 인덱스의 해당 값으로 내림차순 정렬
//ex) classic의 경우 0:500, 2:150, 3:800 -> 3:800, 0:500, 2:150 정렬
List<Integer> indexKeySet = new ArrayList<>(index.get(key).keySet());
Collections.sort(indexKeySet, (o1,o2) -> index.get(key).get(o2).compareTo(index.get(key).get(o1)));문제의 예제를 가지고 설명하자면, {"classic","pop","classic","classic","pop"}라는 장르 배열이 있고, {500,600,150,800,2500} 라는 재생횟수 배열이 있다.
장르를 키로 가지는 totalCount 맵을 생성하면 해당 맵은 [{"classic" : 1450} , {"pop" : 3100}] 으로 구성될 것이다.
마찬가지로, index 맵은 [{"classic" : [{0 , 500} , {2 , 150} , {3 , 800}]} , {"pop" : [{1 , 600} , {4 , 2500}]}]으로 구성될 것이다.
totalCount 맵을 합계 기준 내림차순 정렬하면 [{"pop" : 3100} , {"classic" : 1450}]이 될 것이고,
index 맵을 내림차순 정렬하면 [{"classic" : [{3 , 800} , {0 , 500} , {2 , 150}]} , {"pop" : [{4 , 2500} , {1 , 600}]}]과 같은 형태로 정렬 될 것이다.
이후, totalCount의 keySet을 가지고 index맵에서 차례로 앞의 2개씩을 배열에 넣어주면 된다.
아래는 Java로 구현한 코드이다.
🚩 JAVA 코드
package com.algorithm.Programmers.Lv3;
// 프로그래머스 Lv3 베스트 앨범
import java.util.*;
public class Solution_42579 {
public static void main(String[] args) {
String[] genres = {"classic","pop","classic","classic","pop"};
int[] plays = {500,600,150,800,2500};
solution(genres,plays);
}
public static int[] solution(String[] genres, int[] plays) {
List<Integer> answer = new ArrayList<>();
Map<String,Integer> totalCount = new HashMap<>(); // 합계를 넣어줄 Map
Map<String,Map<Integer,Integer>> index = new HashMap<>(); // 인덱스와 값을 넣어줄 Map
for(int i=0; i< genres.length;i++){
// 키가 있는 경우 인덱스와 값, 합계를 각각 넣어줌
if(totalCount.containsKey(genres[i])){
totalCount.replace(genres[i],totalCount.get(genres[i])+plays[i]);
index.get(genres[i]).put(i,plays[i]);
continue;
}
Map<Integer,Integer> idxAndPlay = new HashMap<>(); // 인덱스와 값을 넣을 Map 생성
totalCount.put(genres[i],plays[i]);
idxAndPlay.put(i,plays[i]);
index.put(genres[i],idxAndPlay);
}
List<String> keySet = new ArrayList<>(totalCount.keySet());
//totalCount Map에서 합계를 기준으로 내림차순으로 정렬
Collections.sort(keySet, (o1,o2) -> totalCount.get(o2).compareTo(totalCount.get(o1)));
//index Map에서 인덱스의 해당 값으로 내림차순 정렬
//ex) classic의 경우 0:500, 2:150, 3:800 -> 3:800, 0:500, 2:150 정렬
for(String key : keySet){
List<Integer> indexKeySet = new ArrayList<>(index.get(key).keySet());
Collections.sort(indexKeySet, (o1,o2) -> index.get(key).get(o2).compareTo(index.get(key).get(o1)));
//상위 두개의 인덱스를 넣어주는데, 한 개인경우 첫번째만 넣어줌
answer.add(indexKeySet.get(0));
if(indexKeySet.size()>1)
answer.add(indexKeySet.get(1));
}
int[] returnValue = new int[answer.size()];
for(int i=0;i<answer.size();i++){
returnValue[i] = answer.get(i);
}
return returnValue;
}
}📄 정리
최근에 시험본 우아한 테크코스 3기의 코딩테스트 6번 문제와 비슷한 유형의 문제였다. 우아한 테크코스 코딩테스트에서는 String배열을 파싱해서 지금 푼 문제와 비슷하게 Map을 구성한 후 문제 조건에 알맞게 풀었으면 되었을텐데 시간에 쫒기다 보니 문제를 풀지 못했다.
베스트 앨범 문제를 풀면서, 코딩 테스트에서 못 푼 문제에 대한 회고를 하게 되었고, 이 문제를 해결한 방식을 적용해서 다시 한번 풀어보는 시간을 가지는 것이 도움이 될 것 같다.
