[알고리즘] Hash - 베스트앨범

JavaScript 스터디에서 알고리즘 문제를 풀고 풀이법을 공유하고 있습니다.

이번 문제는 프로그래머스의 Hash - 베스트앨범 문제입니다. 설명과 제한사항을 먼저 보겠습니다. 풀이코드를 바로 보고 싶으시면 여기를 클릭해주세요.

• 문제설명

  • 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
    • 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
    • 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
    • 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
  • 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

• 제한사항

  • genres[i]는 고유번호가 i인 노래의 장르입니다.
  • plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
  • genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
  • 장르 종류는 100개 미만입니다.
  • 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
  • 모든 장르는 재생된 횟수가 다릅니다.

• 입출력 예시

  ["classic", "pop", "classic", "classic", "pop"],[500, 600, 150, 800, 2500] // 입력값
  // [4, 1, 3, 0] 출력값

---

 

이 문제는 어려웠지만 한번에 풀 수 있었습니다. 여기는 풀이코드로 가기 위한 데이터 변화이니 바로 풀이코드를 보고 싶으시면 여기를 클릭해주세요.

 

장르명을 key로, 장르별 총 재생 수를 value로 갖는 Hash형태의 데이터를 만들고, 그 value(장르별 총 재생 수)로 배열을 만들고 sort()를 이용해 장르별 순위를 정합니다.

{ classic: 1450, pop: 3100 } // 만들어진 Hash 형태의 Object
[ 3100, 1450 ] // sort()를 통해 내림차순 정렬된 재생 수 Array

그 다음 순서를 보장해주는 데이터 타입이면서 Hash형태인 Map을 만들고 정렬된 장르별 총 재생 수 Array의 순서에 따라 key를 해당 장르로 합니다. value는 처음 인자로 들어온 plays에서 key에 맞는 재생 수만 남기고 0으로 바꿉니다.

Map {
  'pop' => [ 0, 600, 0, 0, 2500 ],
  'classic' => [ 500, 0, 150, 800, 0 ]
}

이후 앞서 만들어진 Map과 Map의 value로 이중for문을 돌려 원하는 return을 받습니다.

[4, 1, 3, 0]

 

데이터의 흐름을 알았으니 코드를 짜보도록 합니다. 자신만의 스타일이 있을 것이지만 저는 제 나름대로 짜봤습니다.

 

 

풀이 코드는 아래와 같습니다.

 

 

const solution = (genres,plays) => {
  let answer=[];
  let totalPlayMap = new Map();

  let totalPlayObj = genres.reduce(((acc,item,idx) => {
    if(!acc[item]) {acc[item] = plays[idx];}
    else {acc[item] = acc[item] + plays[idx];}
    return acc;
  }),{})
  let playArr = [...Object.values(totalPlayObj)].sort((x,y) => y - x) // 내림차순 정렬된 재생 수 Array

  for(let item of playArr){
    let key = Object.keys(totalPlayObj).find(key => totalPlayObj[key] === item);
    let arr=[];
    arr.length = genres.length;
    arr.fill(0);
    for(let i=0;i<arr.length;i++){
      if(genres[i] === key){arr[i]=plays[i]}
    }
    totalPlayMap.set(key,arr); // 순서를 보장해주는 데이터 타입이면서 Hash형태인 Map
  }

  for (let [key,value] of totalPlayMap){
    const arr = [...value].sort((a,b) => b - a);
    for(let item of arr){
      if(item === 0 || arr.indexOf(item) === 2){break}
      else {
        answer.push(value.indexOf(item));
        value[value.indexOf(item)] = null;
      }
    }
  }
  return answer;
}

참고로 Array.prototype.sort()는 원본을 변경하는 메소드이므로 그냥 value.sort((a,b) => b - a);를 하면 원본이 변경되어 나중에 value.indexOf(item)이 제대로 작동하지 않을 수 있으니 반드시 value를 복사해서 사용해야 합니다. 하면서 알게 된 것은 Map은 copy가 굉장히 까다롭다는 것입니다. 처음에 value가 아니라 생성한 Map을 복사하려고 했었고 그때 알게 되었고 다시 코드를 보니 value만 복사하면 된다는 걸 알게되었습니다.

 

또 중요한 점이 있는데 재생 수가 동일한 경우 같은 index를 answer에 push할 수 있다는 점입니다. 프로그래머스에서 이런 경우 테스트 케이스 2번, 15번을 통과할 수 없으니, 한번 처리한 value 아이템은 null로 바꿔주는 코드 value[value.indexOf(item)] = null;가 잊지 말도록 합시다.

 

위 코드를 돌리니 다행히 모든 테스트 케이스를 무사히 통과했습니다.

본문에서 사용된 reduce, sort 메소드와 Map 등에 대해서 글을 쓸 기회가 있을 것 같습니다. 당장 사용법이 궁금하시다면 각각 MDN의 Array.prototype.reduce(), Array.prototype.sort(),  Map 공식문서를 참고해주세요.

 

 

이밖에 다른 방법을 알고 있거나 더 효율적인 코드를 아신다면 댓글로 달아주세요. 많은 분들에게 큰 도움이 될 거에요.

 

도움이 되셨다면 좋아요와 댓글 부탁드립니다. 감사합니다~