[JavaScript] 프로그래머스 코딩테스트 레벨 3 : 베스트앨범

📌  문제

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

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

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

📌  제한사항

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

📌  입출력 예

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

---

📌  풀이

알아야 하는 것

• 구조 분해 할당

구할 것

• 가장 많이 재생된 장르 (장르별로 취합)
  • 장르별 재생 수 기준으로 정렬
• 장르를 기준으로 인덱스와 재생횟수 구하기
  • 재생횟수가 높은 순으로 정렬
• 우선순위 2위까지 구하기

 

구할 것은 크게 어떤 장르 노래의 총합이 더 높은지, 그 장르를 기준으로 인덱스 몇 번째의 노래가 재생횟수가 높은지다.

이를 구하기 위해 genreMap, playMap 2개의 맵을 선언하고 정답을 반환할 빈 배열 answer를 선언했다.

 

1) 가장 많이 재생된 장르 (장르별로 취합)

장르를 키값으로, 재생횟수를 밸류값으로 설정해 genreMap에 키-값 쌍을 설정한다.

장르가 들어 있는 배열을 순회하는데 이 때 이미 genreMap에 같은 장르, 즉 같은 키가 들어 있다면 그 키의 밸류 값을 가져와 재생횟수를 누적하여 더해준다. 만약 genreMap에 없는 장르가 들어왔다면 plays 배열의 동일한 인덱스 값을 넣어준다. (장르 배열과 재생횟수 배열은 동일한 길이를 가지고 있다.) 

 

이 때 console.log로 genreMap을 찍어보면 다음과 같이 출력된다.

Map(2) { 'classic' => 1450, 'pop' => 3100 }

 

맵 같은 이터러블 객체는 순서라는 개념은 있지만, 인덱스는 없어서 정렬을 할 수가 없다.

장르별 재생 수 기준으로 정렬하기 위해서는 이 이터러블 객체를 배열로 바꿔준다.

 

전개 구문을 사용해 배열로 만들면 [ 'classic', 1450 ] [ 'pop', 3100 ] 이런 모양이 된다.

이 때 우리는 재생 수를 기준으로 정렬하고 싶은 것이기 때문에, 2차원 배열 [0][1] 중 [1] 값만 비교하면 된다.

let BestGenre = [...genreMap].sort((a, b) => b[1] - a[1]);

 

BestGenre = [ [ 'pop', 3100 ], [ 'classic', 1450 ] ]

이렇게 하면 최종적으로 재생횟수가 더 큰 pop 장르를 우선으로 정렬하게 된다.

 

2) 장르를 기준으로 인덱스와 재생횟수 구하기

장르를 키값으로, 인덱스와 재생횟수를 밸류값으로 한 playMap을 만든다.

처음 했던 것과 같이 plays 배열을 순회하며 playMap에 키-값을 채워 넣는다.

다만 이번에는 누적하는 게 아니라, 같은 키값만 공유한 형태를 유지해야 하기 때문에 playMap 안에 같은 장르가 있다면, 인덱스와 재생횟수를 배열에 추가하도록 한다.

 

이 때 playMap을 console.log에 찍어보면 아래와 같이 구성된다.

하나의 장르를 키값으로, 밸류 값에는 각 인덱스와 재생횟수가 들어가 있다.

Map(2) {
  'classic' => [
    { index: 0, plays: 500 },
    { index: 2, plays: 150 },
    { index: 3, plays: 800 }
  ],
  'pop' => [ { index: 1, plays: 600 }, { index: 4, plays: 2500 } ]
}

 

예를 들어 클래식에서 재생횟수로 2순위까지 든 인덱스를 찾으려면 정렬을 해두면 2순위까지 뜯어가기가 용이하다.

따라서 sort를 해줄 건데, 밸류값을 정렬하되 plays 부분만 내림차순으로 정렬한다.

 

그러면 아래와 같이 playMap도 재생횟수를 기준으로 내림차순이 되어 있다.

Map(2) {
  'classic' => [
    { index: 3, plays: 800 },
    { index: 0, plays: 500 },
    { index: 2, plays: 150 }
  ],
  'pop' => [ { index: 4, plays: 2500 }, { index: 1, plays: 600 } ]
}

 

3) 우선순위 2위까지 구하기

아까 BestGenre = [ [ 'pop', 3100 ], [ 'classic', 1450 ] ] 라고 했다.

이 배열을 순회하면서 pop, classic과 같은 장르만 빼와 해당 장르의 밸류값을 songs라고 하자.

이 배열을 순회하는 이유는 노래를 수록하는 기준 중 [속한 노래가 많이 재생된 장르를 먼저 수록] 해야 하기 때문에 이 배열의 정렬 순서대로 수록을 해줘야 하기 때문이다. (playMap을 배열로 만들어서 순회했더니 classic이 먼저 수록되어 오류가 났다.)

 

songs는 아래와 같이 생겼다.

[ { index: 4, plays: 2500 }, { index: 1, plays: 600 } ]
[
  { index: 3, plays: 800 },
  { index: 0, plays: 500 },
  { index: 2, plays: 150 }
]

이 때 우리는 각 장르별로 노래를 2곡 실을 수 있다.

songs를 순회하면서 인덱스가 0, 1 까지만 돌 수 있도록 2에서는 break를 걸어준다.

이후 빈 배열 answer에 songs의 인덱스(지금 돌고 있는 인덱스)의 진짜 index(실제 객체 안에 들어 있는 인덱스)를 push한다.

 

전체 코드는 아래와 같다.

function solution(genres, plays) {
  let answer = [];
  let genreMap = new Map();
  let playMap = new Map();

  // 가장 많이 재생된 장르순으로 정렬 (pop)
  for (let i = 0; i < genres.length; i++) {
    if (genreMap.has(genres[i])) {
      genreMap.set(genres[i], genreMap.get(genres[i]) + plays[i]);
    } else {
      genreMap.set(genres[i], plays[i]);
    }
  }

  let BestGenre = [...genreMap].sort((a, b) => b[1] - a[1]);
  // [ [ 'pop', 3100 ], [ 'classic', 1450 ] ]

  // 장르 내에서 많이 재생된 노래순으로 정렬
  for (let i = 0; i < plays.length; i++) {
    if (playMap.has(genres[i])) {
      playMap.get(genres[i]).push({ index: i, plays: plays[i] });
    } else {
      playMap.set(genres[i], [{ index: i, plays: plays[i] }]);
    }
  }

    console.log(playMap)
  for (let [k, v] of playMap) {
    v.sort((a, b) => b.plays - a.plays);
  }

  // 정렬된 장르별로 노래 순위 자르기
  for (let i = 0; i < BestGenre.length; i++) {
    let songs = playMap.get(BestGenre[i][0]);
    for (let j = 0; j < songs.length; j++) {
      if (j >= 2) {
        break;
      }
      answer.push(songs[j].index);
    }
  }
  return answer;
}

단계별로 쪼개서 생각하되 순서를 고려하지 않으면 오류가 나서 왜 이런 풀이가 나왔는지 한참 검증해봤다.

이게 최선은 아니겠지만 복잡한 메서드를 사용하지 않고 풀었을 땐 이것이 최선이었다... ㅠㅠ

아직 정렬을 제대로 다루지 못하는 것 같다. 그래도 처음으로 레벨 3 문제를 풀어보았다... ㅠㅠ 어렵다!