베스트 앨범

코딩 테스트 문제

프로그래머스

 

문제 접근)
가장 많이 재생된 장르, 장르 내에서 많이 재생된 노래, genres(장르)와 plays(재생된 횟수)의 길이가 같으며 1~10^4이므로 10^4 * 10^4 = 10^8 이 되므로 시간복잡도는 O(N^2) 미만의 알고리즘으로 풀어야 합니다.

 

정답 및 해설

정답

function solution(genres, plays) {
    let answer = [];
    let genresMap = {}; // 장르
    let playsMap = {}; // 노래 재생 횟수
    
    // 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
    for (let i = 0; i < genres.length; i++) {
        const genre = genres[i]; // 장르 이름
        const play = plays[i]; // 재생 횟수
        
        if (!(genre in genresMap)) {
            genresMap[genre] = [];
            playsMap[genre] = 0;
        }
        
        genresMap[genre].push([i, play]);
        playsMap[genre] += play;
    }
    /* 결과 값
    {
        genresMap: '{"classic":[[0,500],[2,150],[3,800]],"pop":[[1,600],[4,2500]]}',
        playsMap: { classic: 1450, pop: 3100 }
    }
    */
    
    // 노래 재생 횟수 많은 것부터 내림차순 정렬
    const sortedGenres = Object.keys(playsMap).sort((a, b) => playsMap[b] - playsMap[a])
    // 결과 값: { sortedGenres: [ 'pop', 'classic' ] }
    
    
    for (const genre of sortedGenres) {
        sortedSongs = genresMap[genre].sort((a, b) => b[1] - a[1]);
        /* 결과값
        	{ sortedSongs: [ [ 4, 2500 ], [ 1, 600 ] ] }
            { sortedSongs: [ [ 3, 800 ], [ 0, 500 ], [ 2, 150 ] ] }
        */
        answer.push(...sortedSongs.slice(0, 2).map((song) => song[0]));
    }
    
    return answer;
}

해설

우선 재생 횟수가 많은 장르를 추출하고, 그 장르에서 재생 횟수가 많은 순으로 정렬하고 각 장르는 2개씩 묶여서 수록되므로 위와 같은 과정으로 해결하였습니다.