문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 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] |
풀이
해시를 이용하여 풀 수 있는 문제이다. 흔히 자바스크립트에서 해시라고 하면 보통 객체(Object)를 이용하여 풀곤한다. 또는 ES6(ES2015)에서 도입된 Map을 이용해서도 접근할 수 있다. 둘의 차이는 키(key)값으로 사용할 수 있는 값이 객체(Object)의 경우엔 string과 Symbol(ES6)만 가능하지만, Map의 경우엔 number를 제외한 어떤 값도 키로 지정이 가능하다. 또한 대용량의 데이터를 다루는 경우 Map의 접근 속도가 더 빠르다. 해당 풀이에서는 그냥 객체(Object)를 이용해서 풀이하겠다.
문제 설명에서 제시되는 순서대로만 구현하면 큰 문제없이 풀 수 있다. 주어진 genres를 반복문을 돌면서 해당 genre가 객체에 존재하는지 아닌지를 먼저 체크하고, 존재하지 않는 경우 해당 장르의 총 플레이를 저장할 sum에 현재 플레이 횟수를 넣는다. 또한 장르 내에서 또 다시 재생횟수와 고유번호를 가지고 정렬이 필요하므로 list라는 키값에 현재 genre의 고유번호와 플레이 횟수를 저장한다. 만약 이미 해당 장르가 객체에 존재하는 경우에는 기존에 있는 sum에 해당 genre의 플레이 횟수를 더하고, list에 역시 해당 genre의 고유번호와 플레이 횟수를 저장하면 문제풀이에 필요한 key-value 쌍의 해시저장소를 만들 수 있다. reduce를 이용해서 다음과 같이 구현할 수 있다. 아래 코드가 이해가 잘 되지 않는다면 reduce의 사용방법을 먼저 익히는 것을 추천한다.
const hash = genres.reduce((acc, cur, idx) => {
if(acc[cur]) { // 객체에 현재 장르가 있으면
acc[cur].sum += plays[idx];
acc[cur].list[idx] = plays[idx];
} else // 객체에 현재 장르가 없으면 초기화
acc[cur] = {
sum : plays[idx],
list : {
[idx] : plays[idx]
}
}
return acc;
}, {});해시값을 성공적으로 만들었다면 이를 이용하여 문제의 요구조건대로 return 값을 만들어주자. 먼저 많이 재생된 장르 먼저 수록하기위해 각 장르가 가지고 있는 sum을 기준으로 내림차순 정렬을 해준다. sum은 해시의 value에 들어있기 때문에 Object.values(hash)를 통해 배열을 만들고 정렬을 수행할 수 있다.
const sorted = Object.values(hash)
.sort((a,b) => b.sum - a.sum)
.map(el => el.list);
// sorted에는 sum을 기준으로 내림차순 정렬을 먼저 실행하고
// 정렬이 완료된 상태에서 list 목록만 배열로 반환받아 저장한다.sorted 에는 가장 많이 재생된 장르 순으로 해당 장르에 들어있는 리스트가 저장이 되어있다. 우리가 필요한 것은 여기서 다시 index를 추출하는 것이다. 위 hash 구조에서 우리는 index를 키값으로 하여 플레이 횟수를 저장했다. 따라서 Object.keys(someKey)를 통해 반복문을 돌면서 다시 각 키가 가진 value(= 플레이 횟수)를 기준으로 내림차순 정렬을 해준다.
const indexs = sorted.map(list =>
Object.keys(list).sort((a, b) => list[b] - list[a]));
// 위에서 list는 { index : play time } 구조로 이루어진 객체이고
// 해당 list를 key를 기준으로 배열로 만들면 index로 이루어진 배열이 만들어지고
// 다시 list[a] 또는 list[b]로 접근하면 해당 list의 key값이 가진
// value(= play time)에 접근 가능하다.정렬이 완료된 indexs에서 우리는 앞 2개의 곡만 수록하면 된다. 이때 2개 이상의 목록이 항상 존재하지 않을 수 있으므로 해당 값의 유무를 체크해서, 값이 존재하면 answer에 push 하도록 하면 되겠다.
indexs.forEach(genre => {
if(genre[0]) answer.push(+genre[0]);
if(genre[1]) answer.push(+genre[1]);
});
// 위에서 키값에 number를 넣을 수 없다고 했다.
// 때문에 genre[idx]에 들어있는 값은 문자열 처리된 숫자이다.
// return 값은 정수를 원소로 갖는 배열이므로 이를 정수로 만들어주자.코드
function solution(genres, plays) {
const answer = [];
const hash = genres.reduce((acc, cur, idx) => {
if(acc[cur]) {
acc[cur].sum += plays[idx];
acc[cur].list[idx] = plays[idx];
} else
acc[cur] = {
sum : plays[idx],
list : {
[idx] : plays[idx]
}
}
return acc;
}, {});
const sorted = Object.values(hash)
.sort((a,b) => b.sum - a.sum)
.map(el => el.list);
const indexs = sorted.map(list =>
Object.keys(list).sort((a, b) => list[b] - list[a]));
indexs.forEach(genre => {
if(genre[0]) answer.push(+genre[0]);
if(genre[1]) answer.push(+genre[1]);
});
return answer;
}출처
