문제설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한 사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
My solution
// 💡 문제 분석 💡
// In : 노래장르(문자열배열), 노래별재생횟수(정수배열) Out : 노래고유번호(인덱스값)
// 노래 고유번호는 genres 와 plays의 index 값
// 많이 재생 장르 > 많이 재생 노래 > 고유번호 낮은 노래
// -> 장르별 플레이 횟수 총 합 비교 / 장르별 재생횟수 기준 내림차순 정렬 필요
// 해시 문제니까, 해시함수 만들기 : 같은 장르는 같은 해시값, 해시값 인덱스에 리스트로 장르별 노래 목록 나열
function solution(genres, plays) {
let answer = []; // 노래고유번호(인덱스값) 순서대로 담은 배열
const genreInfo = []; // 장르별 해시테이블에 자리한 index 값, 총플레이수, 탑2 리스트 저장할 것
const table = new Array(2000);
for (let i = 0; i < genres.length; i++) { // hash table 만들기
setHashTable(genres[i], plays[i], i, table, genreInfo);
}
for (let i = 0; i < genreInfo.length; i++) { // play 횟수별 genreInfo 배열 정리
let first = 0;
let second = 0;
for (let j = 1; j < table[genreInfo[i].idx].length; j++) {
const playTemp = table[genreInfo[i].idx][j].play; // 현재 노래 플레이 횟수
const playNo = table[genreInfo[i].idx][j].no; // 현재 노래 고유번호
genreInfo[i].play += playTemp; // 총 플레이 수를 더해주고
if (playTemp > first) { // 현재 플레이 수가 제일 높은 플레이수보다 크면 교체
genreInfo[i].top[1] = genreInfo[i].top[0]; // 기존에 있던 것 2순위로
genreInfo[i].top[0] = playNo; // top 리스트에 번호넣어주기
second = first;
first = playTemp;
} else if (playTemp === first) { // 수가 같으면 고유번호 비교
if (genreInfo[i].top[0] > playNo) {
genreInfo[i].top[1] = genreInfo[i].top[0]; // 기존에 있던 것 2순위로
genreInfo[i].top[0] = playNo;
} else if (playTemp > second) { // 두번째것과 비교
genreInfo[i].top[1] = playNo;
second = playTemp;
} else if (playTemp === second) {
if (genreInfo[i].top[1] > playNo) {
genreInfo[i].top[1] = playNo;
}
}
} else if (playTemp > second) { // 두번째 것과 비교
genreInfo[i].top[1] = playNo;
second = playTemp;
} else if (playTemp === second) {
if (genreInfo[i].top[1] > playNo) {
genreInfo[i].top[1] = playNo;
}
}
}
}
genreInfo.sort((a, b) => { // 플레이 횟수순으로 장르 정렬
return b.play - a.play;
});
for (let i = 0; i < genreInfo.length; i++) {
for (let j = 0; j < 2; j++) {
if (genreInfo[i].top[j] !== null) {
answer.push(genreInfo[i].top[j]);
}
}
}
return answer;
}
function setHashTable(genre, play, num, table, genreInfo) {
const idx = hashValue(genre);
while (true) {
if (!table[idx]) { // 처음 등록되는 장르
table[idx] = [genre, { play: play, no: num }]; // 0 idx : 장르, 1~ : 노래들 객체로
genreInfo.push({ idx: idx, play: 0, top: [null, null] });
return;
} else if (table[idx][0] === genre) { // 이미 등록된 장르
table[idx].push({ play: play, no: num });
return;
} else { // 충돌의 경우
idx += hashStep(idx);
idx = idx > table.length ? idx - table.length : idx;
}
}
}
function hashValue(s) {
let hash = 17;
for (let i = 0; i < s.length; i++) {
hash = (13 * hash * s.charCodeAt(i)) % 2000;
}
return hash;
}
function hashStep(idx) {
return 17 - (idx % 17);
}노래 플레이 횟수별로 정렬하는게 너무 길게 작성되었다.
처음에 hash 테이블의 각 인덱스별 배열의 첫번째로 장르이름을 따로 넣으면서 복잡해진 것 같았다..
table[idx] = [genre, { play: play, no: num }]; // 0 idx : 장르, 1~ : 노래들 객체로그래서 이걸 그냥 genre 까지 객체 안에 넣은 로직으로 코드를 수정해봤다.
// #2
function solution(genres, plays) {
let answer = []; // 노래고유번호(인덱스값) 순서대로 담은 배열
const genreInfo = []; // 장르별 해시테이블에 자리한 index 값, 총플레이수, 탑2 리스트 저장할 것
const table = new Array(2000);
for (let i = 0; i < genres.length; i++) { // hash table 만들기
setHashTable(genres[i], plays[i], i, table, genreInfo);
}
for (let i = 0; i < genreInfo.length; i++) {
table[genreInfo[i].idx].sort((a, b) => { // hash table 안, 각 장르안에서 플레이 횟수순으로 정렬
if (b.play > a.play) {
return 1;
} else if (b.play < a.play) {
return -1;
} else {
return a.no - b.no;
}
})
for (let j = 0; j < table[genreInfo[i].idx].length; j++) {
genreInfo[i].play += table[genreInfo[i].idx][j].play; // 총 플레이 수를 더해주기
}
}
genreInfo.sort((a, b) => { // 플레이 횟수순으로 장르 정렬
return b.play - a.play;
});
for (let i = 0; i < genreInfo.length; i++) {
answer.push(table[genreInfo[i].idx][0].no);
if (table[genreInfo[i].idx][1]) {
answer.push(table[genreInfo[i].idx][1].no);
}
}
return answer;
}
function setHashTable(genre, play, num, table, genreInfo) {
const idx = hashValue(genre);
while (true) {
if (!table[idx]) { // 처음 등록되는 장르
table[idx] = [{ genre: genre, play: play, no: num }];
genreInfo.push({ idx: idx, play: 0 });
return;
} else if (table[idx][0].genre === genre) { // 이미 등록된 장르
table[idx].push({ genre: genre, play: play, no: num });
return;
} else { // 충돌의 경우
idx += hashStep(idx);
idx = idx > table.length ? idx - table.length : idx;
}
}
}
function hashValue(s) {
let hash = 17;
for (let i = 0; i < s.length; i++) {
hash = (13 * hash * s.charCodeAt(i)) % 2000;
}
return hash;
}
function hashStep(idx) {
return 17 - (idx % 17);
}배열의 각 요소를 같은 구성의 객체로 통일시키니까, 직접 정렬할필요없이 sort로 정렬할 수 있어서 코드가 좀 더 짧아졌다!
시간복잡도도 비슷한데, 조금 더 직관적인 코드로 짠거같아 뿌듯하다ㅎㅎ
객체 배열을 생성할 땐, 구조를 동일하게 하자!!!
Others
해시를 사용하지 않은 다른사람들의 코드들
// #1
function solution(genres, plays) {
var dic = {};
genres.forEach((t,i)=> {
dic[t] = dic[t] ? dic[t] + plays[i] :plays[i];
});
var dupDic = {};
return genres
.map((t,i)=> ({genre : t, count:plays[i] , index:i}))
.sort((a,b)=>{
if(a.genre !== b.genre) return dic[b.genre] - dic[a.genre];
if(a.count !== b.count) return b.count - a.count;
return a.index - b.index;
})
.filter(t=> {
if(dupDic[t.genre] >= 2) return false;
dupDic[t.genre] = dupDic[t.genre] ? dupDic[t.genre]+ 1 : 1;
return true;
})
.map(t=> t.index);
}
- 장르별 총 재생횟수를 저장한 객체 dic 생성
: genres 배열을 각 요소(장르명)마다 방문하면서 dic 객체의 해당 장르명으로 된 속성의 값이 존재하는지 확인- 존재하지 않으면 : dic의 해당 장르명(genres[i])의 속성 값으로 해당 곡의 재생횟수 저장(plays[i])
- 존재하면 : 기존 속성값에 해당 곡의 재생횟수 더해주기
- map 을 통해 노래별 정보(장르, 재생횟수, 고유번호)를 담은 객체 리스트 만들기
- sort 로 정렬
- 먼저, 장르 이름별로 정렬 : 장르이름이 다를경우, 만들어놓은 dic 객체를 통해 재생횟수 순으로 정렬
- 두번째, 장르 이름이 같다면 : 각 노래의 재생횟수 순으로 정렬
- 마지막, 재생횟수까지 같다ㅏ면 : 고유번호가 작은 순서대로 정렬
- filter 로 상위 2개만 true, 그 이상은 false 로 제외해주기
: dupDic 객체를 만들어, 각 장르명의 속성값을 해당 장르가 나올때마다 +1 로 카운트
- 마지막 map으로 고유번호만 출력
코드가 깔끔하고 이해하기 쉽다.
이 문제도 굳이 해시 함수를 거칠 필요없이 객체 리터럴로 데이터를 직접 저장해서 정렬하면 됐다.
Reference
공부중인 개발자