[프로그래머스 FE 데브코스] 해시 문제 : 베스트 앨범

오늘은 오프 멘토님과의 첫 번째 커피챗이 있는 날이네요! 기대됩니다. 🤩
오늘 강사님께서 해시와 고차함수들을 이용한 문제와 linked list를 이용한 Queue 문제를 풀어주셨는데 저는 조금 어렵더라고요.
한번 차근차근 다시 풀어봐야겠어요. 제 것으로 만들면 다른 문제 풀 때에도 분명 도움이 많이 될 거 같아요.

+ 저녁에 커피챗 시간을 가졌는데 생각할게 많아졌어요.. 아직 너무 학생 같은 마인드로 강의 듣고 복습하고 하는 식의 공부만 했던 게 아닌가라는 생각이 들면서 좀 더 능동적으로 필요한 공부를 찾아서 해야겠다는 생각을 했어요. 지금 내가 부족하고 필요한 부분을 찾아서 책임지고 설명할 수 있을 정도로 깊게 공부하고 정리해야겠더라고요. 차근차근 지치지 말고 해 봐야겠습니다!
다음 커피챗도 기대됩니다!

 

🔗 해시 문제 : 베스트 앨범 

 

✔️ 입출력 예

 

✔️ 입출력 예 설명

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번 노래는 수록되지 않습니다. 

 

⭐️ 처음 읽었을때는 몰랐는데 입출력 예 설명 부분을 참고하면 문제 풀이 순서를 정하기 수월하더라고요. 
같은 장르끼리 묶고  ➡️  묶인 노래들을 재생 순으로 정렬하고  ➡️  노래를 2개까지 자릅니다. 

 

genres가 문자열 배열로 되어 있는데 매번 순회를 하면 느려질것이기에 필요한 정보를 하나로 묶기 위해 hash table을 사용하는 것이 좋아요! 자바스크립트에서는 Object나 Map를 사용할 수 있습니다.  이 문제에서는 Map()을 사용할 건데 이유는 기존 객체와는 다르게 key 값으로 객체나, 배열 같은 복잡한 타입도 key로 사용할 수 있고, 여러 편한 메서드를 제공해 주고, 순회도 편하게 해 주기 때문입니다. 

💡 묶는다는 키워드가 나오면 hash table를 생각해 보는 것이 좋습니다!

❓Hash table
key와 value를 받아 key를 해싱하여 나온 index에 값을 저장하는 선형 자료 구조 입니다. 
삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행합니다. 

 

function solution(genres, plays) {
	const genreMap = new Map();
}

 

다음으로는 계산하기 편하도록 genres배열과 plays배열을 하나로 묶어 줍니다. 

 

function solution(genres, plays) {
	const genreMap = new Map();
    genres
    	.map((genre, index) => [genre, plays[index])
}

//실행한 결괏값
 [["classic",500],["pop",600],["classic",150],["classic",800],["pop",2500]]

 

이제 forEach를 이용해서 묶은 배열에서 데이터 뽑아볼게요.

비구조화 할당을 이용하면 더 간단한 코드를 사용 할 수 있습니다. 

genreMap에 set()를 이용해서 key : value 쌍을 넣어줍니다. 

data에 초기값이 없으면 undefined 에러가 뜨니까 data의 초기값도 설정해 줍니다. 

 

function solution(genres, plays) {
  const genreMap = new Map();
  genres
    .map((genre, index) => [genre, plays[index]])
    .forEach(([genre, play], index) => {
      const data = genreMap.get(genre) || {total: 0, songs: []};
      genreMap.set(genre, {
          total: data.total + play,
          songs: [...data.songs, {play, index}]
            .sort((a, b) => b.play - a.play)
            .slice(0, 2)
      })
  })
    console.log(genreMap.get('classic'))
} 

//genreMap의 classic 장르의 출력값을 확인해 봤어요.
{
  total: 1450,
  songs: [ { play: 800, index: 3 }, { play: 500, index: 0 } ]
}

 

저는 songs: [...data.songs, {play, index}] 부분의 {play, index} 부분이 조금 헷갈리더라구요.

이게 어떻게 출력될지 감이 안 잡힌달까...

[{ play: 800, index: 3 }, { play: 500, index: 0 }] 로 key: value으로 출력되더라고요? 

 

제가 헷갈렸던 이유가 객체로 묶었는데 배열처럼 생각했던게 문제였던 거 같아요. 

만약 songs: [...data.songs, [play, index]] 이 코드로 사용했다면 [ [ 800, 3 ], [ 500, 0 ] ] 와 같이 출력됐겠죠?

 

❗️ 하지만 저희는 객체로 묶어주고 구조분해할당을 사용했으므로 [{ play: 800, index: 3 }, { play: 500, index: 0 }] 이렇게 출력되는 것이 어쨌든 맞습니다. (배열로 풀어도 풀리기는 할 거 같아요.)

 

이제 genreMap 객체에서 데이터를 뽑아와서 return 해줘야 합니다.
genreMap 객체를 출력해서 한번 더 확인해 볼게요!
예쁘게 잘 정리되있네요!

 

Map(2) {
  'classic' => { total: 1450, songs: [ { play: 800, index: 3 }, { play: 500, index: 0 } ] },
  'pop' => { total: 3100, songs: [ { play: 2500, index: 4 }, { play: 600, index: 1 } ] }
}

 

그다음 Object.entries() 메서드를 이용하면  [key, value] 쌍의 배열이 반환됩니다. 

 

function solution(genres, plays) {
  const genreMap = new Map();
  genres
    .map((genre, index) => [genre, plays[index]])
    .forEach(([genre, play], index) => {
      const data = genreMap.get(genre) || {total: 0, songs: []};
      genreMap.set(genre, {
          total: data.total + play,
          songs: [...data.songs, {play, index}]
            .sort((a, b) => b.play - a.play)
            .slice(0, 2)
      })
  })
    console.log([...genreMap.entries()])
}

//출력 결과 
[
  [ 'classic', { total: 1450, songs: [ { play: 800, index: 3 }, { play: 500, index: 0 } ] } ],
  [ 'pop', { total: 3100, songs: [ { play: 2500, index: 4 }, { play: 600, index: 1 } ] } ]
]

 

 

이제 정렬만 하면 되는데 total 높은 장르인 pop이 먼저 정렬되게 하고, flatMap() 메서드를 이용해서 songs를 묶어서 정렬해 줍니다.

 

❗️flatMap() 이 아닌 map()을 사용해 버리면 배열(리스트) 안에 리스트가 들어간 너무 복잡한 형태가 되어 버려요.

 

//flatMap() 사용시
[
  { play: 2500, index: 4 },
  { play: 600, index: 1 },
  { play: 800, index: 3 },
  { play: 500, index: 0 }
]

//map() 사용시
[
  [ { play: 2500, index: 4 }, { play: 600, index: 1 } ],
  [ { play: 800, index: 3 }, { play: 500, index: 0 } ]
]

 

정말 마지막으로 index만 뽑아서 정렬해 주면 됩니다!

 

function solution(genres, plays) {
  const genreMap = new Map();
  genres
    .map((genre, index) => [genre, plays[index]])
    .forEach(([genre, play], index) => {
      const data = genreMap.get(genre) || {total: 0, songs: []};
      genreMap.set(genre, {
          total: data.total + play,
          songs: [...data.songs, {play, index}]
            .sort((a, b) => b.play - a.play)
            .slice(0, 2)
      })
  })
    return [...genreMap.entries()]
            .sort((a, b) => b[1].total - a[1].total)
            .flatMap(item => item[1].songs)
            .map(song => song.index)   
    
}

 

실행 결과 [4, 1, 3, 0] 이 잘 나오네요!

 

공부할 거리가 많았고 재밌는 문제 같습니다!

코테에서 만나지는 말자....