[프로그래머스] 해시 _ 베스트 앨범 Lv3, javascript

2021_12_20 알고리즘 스터디 문제 풀이

문제 URL 

코딩테스트 연습 - 베스트앨범

문제

 

수도코드

result 배열 선언
 1. 속한 노래가 많이 재생된 장르를 먼저 수록 (플레이 순위가 높은 장르명을 배열로 추출)
  countedGenres 상수 선언, genres 배열에 reduce를 사용하여 객체에 저장
      만약 acc[cur.genre]가 존재한다면, 
          기존 값에 cur.plays를 더한다
      그렇지 않다면, 키를 갖고, cur.plays를 할당

	sortedGenres 배열을 선언 (객체를 배열로 만들기 위함)
    countedGenres 객체를 순회하며, sortedGenres에 {genre : 'classic', plays : 1000 } 의 형태로 저장 


객체 내의 값 인스턴스 개수 세기 (reduce)
상수 songObj 선언, genres를 Reduce를 사용, 각 장르에 해당하는 곡들을 고유 넘버(id)와 함께 배열의 형태로 저장

 변수 선언
for key of obj로 배열을 순회하면서 arr에 객체 형태로 push Ex) [{genre : 'classic', play : 1000}, ...]
sortedGenres = arr을 sort 메소드로 높은 순 정렬하고 map으로 장르만 추출한다. 그것은 곧 속한 노래가 많이 재생된 장르 순서

2. 장르 내에서 많이 재생된 노래를 먼저 수록
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 인덱스가 낮은 노래를 수록

sortedGenres를 순회,objGenres 객체에서 sortedGenres[j]를 키로 갖는 값은 노래가 요소인 배열
그 배열을 sort 메소드를 사용, play값을 기준 내림차순 정렬하고, 그 값이 같다면, id가 더 낮은 것을 기준으로 정렬
정렬한 그 배열에서 인덱스 0의 값을 result에 추가한다.
그리고 그 배열의 길이가 1이상일 경우 인덱스 1의 값도 result에 추가한다

 

풀이

function solution(genres, plays) {
    let result = [];
    
    const countedGenres = genres.reduce((allGenres, genre, curIdx) =>{
      if (genre in allGenres) {
        allGenres[genre] += plays[curIdx];
      }
      else {
        allGenres[genre] = plays[curIdx];
      }
      return allGenres;
    }, {});
    
    const sortedGenres = [];
    for (const genre in countedGenres) {
        sortedGenres.push({genre , plays :  countedGenres[genre] });
    }
    sortedGenres.sort((a, b) => b.plays - a.plays);

    const songObj = genres.reduce((acc, cur, curIdx) => {
        const tempValue = {id : curIdx, plays : plays[curIdx]}
        if (cur in acc) {
            acc[cur] = acc[cur].concat(tempValue);
        } else {
            acc[cur] = [tempValue];
        }
            return acc;
    }, {})
    
    for (const genreObj of sortedGenres) {
        songObj[genreObj.genre].sort((a, b) => {
            if (a.plays === b.plays) return a.id - b.id;
            return b.plays - a.plays
        })
        result.push(songObj[genreObj.genre][0].id);
        
        if (songObj[genreObj.genre].length > 1) {
            result.push(songObj[genreObj.genre][1].id)    
        }
    }
    return result;
}

 

O(n^2)의 시간 복잡도를 가진 코드를 완성했다.