문제 요약
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래 두 개씩 모아 베스트 앨범을 출시하려 한다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록한다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
노래의 장르를 나타내는 문자열 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] |
풀이 과정
우선 문제에서 고유 번호가 계속해서 나오고 있고 genres와 plays 배열의 길이가 같다. 따라서 두 배열의 인덱스는 공통된 고유 번호를 가리키고 이 번호를 사용해서 어떤 노래인지 구분할 수 있다.
풀이를 위해 어떤 데이터 형식이 필요한가? 입출력 예시를 보았을 때
{
classic: {
'0': 500,
'2': 150,
'3': 800,
'total': 1450
},
pop: {
'1': 600,
'4': 2500,
'total': 3100
},
} 이런식으로 데이터가 만들어지면, 장르별 총 합을 구하고, 장르별 내림차순 정렬을 통해 원하는 새로운 배열을 만들 수 있을 것이라 생각했다. 따라서 Map을 사용하도록 한다.
코드를 작성하기 전 한 가지 간과하고 있었던 점은 genres 배열에서 같은 장르가 중복되서 들어있기 때문에 중복을 제거하고 필요한 장르의 갯수만 사용할 수 있도록 만들어야 한다. 이 때는 Set을 사용하도록 한다.
const set = new Set(genres);Set을 실행하고 나면, {'classic', 'pop'}을 얻을 수 있다. 이 set을 사용해서 장르에 해당하는 객체를 생성한다.
const set = new Set(genres);
const map = new Map();
set.forEach((i) => {
map.set(i, {'total': 0});
}map을 console.log로 확인하면
Map { 'classic' => { total: 0 }, 'pop' => { total: 0 } }처음에 원했던 데이터 형태와 비슷하게 만들 수 있다.
이후에는 이 map에 장르별 고유 번호를 사용해서 데이터를 채워준다.
for(let i = 0; i < plays.length; i++) {
const pre = map.get(genres[i]);
pre[i] = plays[i];
pre['total'] += plays[i];
}plays, genres 배열의 길이만큼 반복하면서 map에서 장르를 가져와서 새로운 데이터를 추가한다.
total은 각 장르의 총 재생횟수이기 때문에 누적해서 계산한다.
다시 map을 확인해보면
Map {
'classic' => { '0': 500, '2': 150, '3': 800, total: 1450 },
'pop' => { '1': 600, '4': 2500, total: 3100 }
}이렇게 처음 만들려고 했던 데이터 형태로 데이터를 정리하였다.
이제 부터는 장르마다 total을 사용해서 어떤 장르의 우선 순위가 높은지 구분하고, 각 장르마다 재생 횟수가 높은 노래가 앞으로 올 수 있도록 만들어야 한다.
정답 같은 오답 시작
여기서 부터 total을 왜 넣고 시작했는지... total 때문에 sort 함수를 사용하는데 문제가 많았었다. 그래도 처음부터 다시 시작하기 보다는 우선 생각한대로 구현하고 싶었기 때문에 계속 사용했었다.
map.forEach((item) => {
const objArr = Object.entries(item);
objArr.sort((a,b) => {
return b[1] - a[1];
})
filteredArr.push(objArr);
})
filteredArr.sort((a, b) => {
return b[0][1] - a[0][1]
})Object.entries를 사용해서 Map에 있는 객체들을 배열로 바꿔준다.
[ [ '0', 500 ], [ '2', 150 ], [ '3', 800 ], [ 'total', 1450 ] ]
[ [ '1', 600 ], [ '4', 2500 ], [ 'total', 3100 ] ]여기서 장르의 총 재생횟수를 나타내는 total이 각 배열의 가장 마지막에 위치하고 있다. 추후에 total을 정리하기 위해서라도 정렬을 통해서 가장 앞으로 이동 시킨다. (왜 그랬을까...) objArr에서 각 배열의 두 번째 인덱스를 사용해서 정렬한다. 정렬 결과
[ [ 'total', 1450 ], [ '0', 500 ], [ '2', 150 ], [ '3', 800 ] ]
[ [ 'total', 3100 ], [ '1', 600 ], [ '4', 2500 ] ]total이 맨 앞으로 이동 되었다. 이제는 이 total값으로 전체 배열을 정렬한다.
따라서 결과적으로 배열은 다음과 같이 변경된다.
[ [ 'total', 3100 ], [ '1', 600 ], [ '4', 2500 ] ]
[ [ 'total', 1450 ], [ '0', 500 ], [ '2', 150 ], [ '3', 800 ] ]변경된 배열을 사용해서 각 배열의 두 개씩을 결과로 사용할 배열에 push 한다.
const resultArr = filteredArr.map((item) => {
const returnArr = item.filter((i) => {
return i[0] !== 'total'
})
return returnArr;
})
resultArr.map((item, idx) => {
if(item.length > 1) {
returnArr.push(+item[0][0])
returnArr.push(+item[1][0])
} else {
returnArr.push(+item[0][0])
}
})여기서 불필요한 로직이 추가된다. total을 제거하기 위해서 filter를 사용해야 했다. total이 없는 배열을 사용해서 만약 배열의 길이가 1일 경우 (0개일 경우는 존재하지 않는다. 1개일 경우는 존재할 수 있음) 고유번호로 저장되어 있는 인덱스 값(string)을 숫자로 변환해서 배열에 push 한다.
결과적으로 정답과 일치하는 배열을 얻어 낼 수 있다.
전체 코드
function solution(genres, plays) {
const filteredArr = [];
const returnArr = [];
const set = new Set(genres);
const map = new Map();
set.forEach((i) => {
map.set(i, {"total": 0});
})
for(let i = 0; i < plays.length; i++) {
const pre = map.get(genres[i]);
pre[i] = plays[i]
pre["total"] += plays[i]
}
map.forEach((item) => {
const objArr = Object.entries(item);
objArr.sort((a,b) => {
return b[1] - a[1];
})
filteredArr.push(objArr);
})
filteredArr.sort((a, b) => {
return b[0][1] - a[0][1]
})
const resultArr = filteredArr.map((item) => {
const returnArr = item.filter((i) => {
return i[0] !== 'total'
})
return returnArr;
})
resultArr.map((item, idx) => {
if(item.length > 1) {
returnArr.push(+item[0][0])
returnArr.push(+item[1][0])
} else {
returnArr.push(+item[0][0])
}
})
return returnArr;
}여기까지만 보면 정답으로 넘어갈 수 있는 부분이었지만 테스트 케이스를 하나 추가해서 확인해 보았을 때 의도하지 않은 버그가 발생했다...
테스트 케이스 추가
| genres | plays | return |
|---|---|---|
| ["classic", "pop", "classic", "classic", "pop", "jazz"] | [500, 600, 150, 800, 2500, 3000] | [4, 1, 5, 3, 0] |
jazz라는 장르를 추가했고 1개의 노래만 갖고 있으며 총 재생횟수는 3000번으로 두 번째로 가장 많이 재생된 장르가 된다.
이 때 기존 코드로 실행했을 때 아래 코드를 실행하고 filteredArr을 콘솔로 확인했을때
filteredArr.sort((a, b) => {
console.log(a[0][0],b[0][0])
return b[0][1] - a[0][1]
}) [
[ [ 'total', 3100 ], [ '4', 2500 ], [ '1', 600 ] ],
[ [ '5', 3000 ], [ 'total', 3000 ] ],
[ [ 'total', 1450 ], [ '3', 800 ], [ '0', 500 ], [ '2', 150 ] ]
]다음과 같은 결과가 출력된다는 것을 알았다. 문제 없이 통과된 이유는 ['5', 3000] 한 개의 노래만 갖고 있는 장르이기 때문에 한 개의 노래 재생횟수가 총 재생횟수와 같아서 결과적으로 정렬하는데 문제가 없었던 것이었고 또한 마지막에 total을 제거했기 때문에 마지막 출력에서는
[
[ [ '4', 2500 ], [ '1', 600 ] ],
[ [ '5', 3000 ] ],
[ [ '3', 800 ], [ '0', 500 ], [ '2', 150 ] ]
]이와 같이 정상적으로 데이터가 만들어졌을 것이다. 문제가 없다고 판단할 수 있지만 의도했던 total이 과연 필요한가 의문이 들었고 코드를 수정했다. (근데 이미 제출을 해버렸네..)
수정한 코드
function solution(genres, plays) {
const filteredArr = [];
const returnArr = [];
const set = new Set(genres);
const map = new Map();
set.forEach((i) => {
map.set(i, {"total": 0});
})
for(let i = 0; i < plays.length; i++) {
const pre = map.get(genres[i]);
pre[i] = plays[i]
pre["total"] += plays[i]
}
map.forEach((item) => {
const objArr = Object.entries(item);
filteredArr.push(objArr);
})
filteredArr.sort((a,b)=>{
return b[b.length-1][1] - a[a.length-1][1]
})
const resultArr = filteredArr.map((item) => {
const returnArr = item.filter((i) => {
return i[0] !== 'total'
})
return returnArr;
}).map((item) => item.sort((a,b) => b[1] - a[1]))
resultArr.map((item, idx) => {
if(item.length > 1) {
returnArr.push(+item[0][0])
returnArr.push(+item[1][0])
} else {
returnArr.push(+item[0][0])
}
})
return returnArr;
}크게 변화한 점은 없지만 total을 배열의 가장 앞으로 이동시키는 로직을 제거하고 총 재생횟수를 사용해서 배열을 정렬할 때 가장 마지막에 있는 total을 사용하도록 변경하였다. 또한 total을 제거한 상태에서 각 배열을 정렬하였다.
정리
데브코스 기간에 한번 접했던 문제인데 그 때 당시만해도 Map, Set을 사용하는 법을 몰랐고 그렇게 풀었었는지 기억도 안난다. 오랜시간 투자하고도 풀지 못해서 결국에는 강사님의 해설 강의만 들었던 것으로 기억하는데, 지금 이 방법이 좋은 방법이라고는 할 수 없지만 내가 생각해서 처음부터 끝까지 풀었기 때문에 나름 재미있었다.
이 방법이 절대 정답은 아닙니다. 아마 오답에 더 가까울거에요...
