[프로그래머스] 해시 - 베스트앨범 문제 풀이

오늘은 처음으로 Level 3 난이도 문제 풀이를 시작하겠습니다. Level 3 난이도 첫 문제는 해시 알고리즘을 활용하는 문제 중 베스트앨범입니다. 그럼 베스트앨범 문제 풀이를 시작하겠습니다.

 

 

프로그래머스 > 해시 > 베스트앨범 문제 풀이

 

 

 

 

‡ 문제 정보

• 문제명: 베스트앨범
• 문제 난이도: Level 3
• 문제 푼 사람 수 : 22221명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

‡ 문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

 

 

역시 Level 3 난이도 문제라 그런지 문제가 한번 꼬여있는 듯합니다. 그럼 문제 설명 해보겠습니다.

• 장르 별 가장 많이 재생된 노래  두 개씩 모아 베스트 앨범 만들기
• Inputs
  • genres: 노래의 장르(String 배열)
  • plays: 노래별 재생 횟수(Integer 배열)
• Output: 베스트 앨범에 들어갈 노래의 고유 번호 순서

 

 

 

 

‡ 제한 사항

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

 

 

• genres[i] = 고유번호가 i인 노래의 장르
• plays[i] = 고유번호가 i인 노래의 재생 횟수
• 1 ≤ genres의 길이 = plays의 길이 ≤ 10,000
• 장르의 종류 < 100
• 장르에 속한 곡이 하나라면 하나의 곡만 선택
• plays에 있는 숫자는 모두 다르다.

 

 

 

 

‡ 입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

 

 

 

 

‡ 입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

   ● 고유 번호 3: 800회 재생
   ● 고유 번호 0: 500회 재생
   ● 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

   ● 고유 번호 4: 2,500회 재생
   ● 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

   ●  장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

 

 

 

 

‡ 알고리즘 만들기

1. 장르명을 key로, [노래 index, 재생횟수]를 value로 가지는 해시 테이블를 배열로 만든다.
2. 1번에서 만든 해시 테이블을 통해 장르별 전체 곡 재생수를 담고 있는 장르 리스트를 만든다.
3. 2에서 만든 장르 리스트를 곡 재생수를 내림차순으로 정렬한다.
4. 장르 리스트 순서대로 장르에 속해있는 최대 재생 수 2곡을 순서대로 담은 리스트를 반환한다.

 

 

 

 

‡ 코드 구현

function solution(genres, plays) {
    // 1. 장르명을 key로, [노래 index, 재생횟수]를 value로 가지는 해시 테이블를 배열로 만든다.
    const genresByHash = genres.reduce((prev, cur, index) => {
        if(typeof prev[cur] !== 'object') {
            prev[cur] = [[index, plays[index]]];
        } else {
            prev[cur].push([index, plays[index]]);
        }
        return prev;
    }, []);
    
    // 2. 1번에서 만든 해시 테이블을 통해 장르별 전체 곡 재생수를 담고 있는 장르 리스트를 만든다.
    let genresList = [];
    for(let genreName in genresByHash) {
        genresByHash[genreName].sort((a, b) => ((b[1] - a[1])));
        const allPlayCount = genresByHash[genreName].reduce((prev, cur) => {
            return prev + cur[1];
        }, 0);
        genresList.push([genreName, allPlayCount]);
    }
    // 3. 2에서 만든 장르 리스트를 곡 재생수를 내림차순으로 정렬한다.
    genresList.sort((a, b) => (b[1] - a[1]));

    // 4. 장르 리스트 순서대로 장르에 속해있는 최대 재생 수 2곡을 순서대로 담은 리스트를 반환한다.
    const answer = genresList.reduce((prev, cur) => {
        const length = genresByHash[cur[0]].length;
        for(let i = 0; i < (length > 2 ? 2 : length); i++) {
            prev.push(genresByHash[cur[0]][i][0]);
        }
        return prev;
    }, []);

    return answer;
}

 

 

 

 

‡ 채점 결과

 

 

이번 문제는 정확성 테스트 케이스만 15개로 문제 풀이에 참고하시기 바랍니다. 

이번에도 효율적으로 정확성 테스트 케이스 15문제를 모두 간결하게 통과하여 베스트앨범 문제 풀이를 완료하였습니다.

이번 문제는 Level 3의 난이도를 갖고 있었던 만큼 알고리즘부터 코드 구현까지 기존 문제 풀이 과정보다 복잡했던 것 같습니다. 더 배워서 보다 효율적으로 문제 풀어 함께 공부하기 쉽도록 풀어보겠습니다.