[알고리즘] 프로그래머스 / 베스트앨범 / Level 3

정보

• 문제 : 프로그래머스 - 베스트앨범
• 분류 : 해시
• 난이도 : Level 3

해결 방법 (생각의 흐름)

1. 장르별 전체 재생 횟수 관리하기

문제 조건에 '많이 재생된 장르의 순서'대로 값을 출력하라는 말이 있기 때문에, 전체 재생 횟수를 관리해야 한다고 생각했다.

입력값에는 아래와 같은 정보가 들어있다.

• 각 노래의 장르 (genres)
  - ["classic", "pop", "classic", "classic", "pop"]
• 각 노래의 재생횟수 (plays)
  - [500, 600, 150, 800, 2500]

genreToPlayCount Map 자료구조를 만들어 장르의 전체 재생 횟수를 관리할 수 있다.

• key : 장르
• value : 해당 장르의 전체 재생 횟수

입력값이 배열이므로, 전체를 순회하여 genreToPlayCount의 값을 채워넣을 수 있다.

2. 장르별 포함하고 있는 노래의 정보를 저장하기

장르별로 어떤 노래를 가지고있는지 저장할 필요가 있다고 생각했다.
정보를 알고싶은 장르가 선택되고나면, 해당 장르의 노래 정보를 바로 가져다가 조작하는게 합리적이라고 생각했기 때문이다.

따라서, genreToSongList Map 자료구조를 만들었고 1번과 마찬가지로 전체 배열을 순회해 데이터를 저장해두었다.

여기까지 작업 코드는 아래와 같다.

const genreToPlayCount = new Map();
const genreToSongList = new Map();

for(let i = 0; i < genres.length; i++) {
  const [genre, playCount] = [genres[i], plays[i]];
  const prevPlayCount = genreToPlayCount.get(genre) || 0;
  genreToPlayCount.set(genre, prevPlayCount + playCount);

  const prevSongList = genreToSongList.get(genre) || [];
  genreToSongList.set(genre, prevSongList.concat({ play: playCount, idx: i }));
}

문제에서는 노래의 id를 배열의 idx로 관리하는데, 위의 Map을 만드는 과정에서 idx가 모두 깨져버리므로 genreToSongList의 노래정보에 idx도 추가해주었다.

3. 전체 재생횟수에 따라 장르를 구분하기

문제에 아래와 같은 조건이 있다.

모든 장르는 재생된 횟수가 다릅니다.

이 말을 곱씹어 생각해보니, 굳이 key값을 장르로하는 Map을 만들 필요가 없어보였다. 그리고 아래와 같은 플로우를 생각할 수 있었다.

1. 전체 재생 횟수에 따라 정렬을 한다.
2. 정렬된 재생 횟수에 배열에서 정보를 얻고자하는 원소를 선택한다.
3. 이와 매핑되는 장르를 선택을 할거다.
4. 선택된 장르를 key로 genreToSongList에서 노래 정보를 꺼내와 추가 작업을 진행한다.

이를 위해 아래와 같은 totalCountToGenre Map을 만들었다.

const totalCountToGenre = new Map();
genreToPlayCount.forEach((totalCount, genre) => {
  totalCountToGenre.set(totalCount, genre);
})

(근데 사실 조금 마음에 안들기는 했다. 그 이유는 아래 생각이나 느낀점에 적어두었다.)

4. 어떤 장르의 노래를 가장 많이 들었을까?

이제 출력을 준비해야한다.

가장 재생 횟수가 많은 장르 순으로 정렬을 해야한다.

Array.from(genreToPlayCount.values())
    .sort((a, b) => b - a)	// 장르의 재생 횟수가 가장 많은 것부터 내림차순 정렬

위의 코드를 통해 가장 많이 들은 장르의 재생 횟수는 알 수 있지만, 어떤 장르인지는 알 수 없다.

const genre = totalCountToGenre.get(playCount);	// playCount : 위의 배열의 원소 중 하나

그래서 3번 과정에서 이를 매핑해주는 Map을 만들었다. 이제 장르를 알 수 있다.

5. 가장 많이 들은 장르의 노래부터 최대 2개씩 꺼내오기

장르별로 어떤 노래를 가지고 있는지는 2번에서 만든 genreToSongList Map을 통해 얻어올 수 있다.

해당 노래 리스트에서는 아래와 같은 조건대로 정렬을 수행해야한다.

• 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다.
• 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

이는 자바스크립트의 Array.prototype.sort() 함수를 이용해 해결할 수 있다.

4번 ~ 5번 과정을 정리한 코드는 아래와 같다.

Array.from(genreToPlayCount.values())
  .sort((a, b) => b - a)
  .reduce((ans, playCount) => {
    const genre = totalCountToGenre.get(playCount);
    const songList = genreToSongList.get(genre);
    const sortedSongList = songList
      .sort((a, b) => a.play === b.play ? a.idx - b.idx : b.play - a.play)
      .slice(0, 2);
  	ans.push(...(sortedSongList.map(item => item.idx)));
  	return ans;
  }, []);

전체 코드

깃허브 소스코드

const solution = (genres, plays) => {
    const genreToPlayCount = new Map();
    const genreToSongList = new Map();
    
    for(let i = 0; i < genres.length; i++) {
        const [genre, playCount] = [genres[i], plays[i]];
        const prevPlayCount = genreToPlayCount.get(genre) || 0;
        genreToPlayCount.set(genre, prevPlayCount + playCount);
        
        const prevSongList = genreToSongList.get(genre) || [];
        genreToSongList.set(genre, prevSongList.concat({ play: playCount, idx: i }));
    }

    const totalCountToGenre = new Map();
    genreToPlayCount.forEach((totalCount, genre) => {
        totalCountToGenre.set(totalCount, genre);
    })
    
    return Array.from(genreToPlayCount.values())
        .sort((a, b) => b - a)
        .reduce((ans, playCount) => {
            const genre = totalCountToGenre.get(playCount);
            const songList = genreToSongList.get(genre);
            const sortedSongList = songList
                .sort((a, b) => a.play === b.play ? a.idx - b.idx : b.play - a.play)
                .slice(0, 2);
            ans.push(...(sortedSongList.map(item => item.idx)));
            return ans;
        }, []);
};

그냥 생각이나 느낀점

• 문제를 꼼꼼히 읽어야겠다. 처음에는 장르도 전체 재생횟수 많은 순으로 상위 2개만 선택하는 것인줄 알고 넘 복잡하게 생각해서 시간 날렸다.
• Map과 Object의 차이점 다시 읽고 정리해두면 좋을 것 같다.
• genreToSongList의 값을 최신화 할 때, 기존 배열에 concat을 붙여서 새로 배열을 만들었다. 사실 입력값이 크면 메모리 문제가 발생할 수 있을 것 같아서 별로 맘에 안든다. (왜 선택했냐면, 저렇게 안하니깐 코드가 넘 더러워져서..)
• totalCountToGenre 맵 객체를 만들었는데, genreToPlayCount에 값을 모두 넣은 뒤 key-value 값만 바꾸는 느낌이라.. 굳이 Map을 각각 만들어야하나? 하는 생각이 들었다. 지금 생각해보니 안만들고 기존꺼(genreToPlayCount에) 쓰면 될 것 같은데 한 번 작업해봐야겠다.
• 비슷하게 genreToPlayCount, genreToSongList 요것도 같은 key값으로 value만 다르게 관리되고 있는데 하나로 합칠수도 있을 것 같다.
• 알고리즘 어렵다.

참고 자료

• Map vs Object