[알고리즘] 프로그래머스-해시-베스트앨범 풀이(feat. JS)

BigChoi·2022년 3월 7일
0

알고리즘

목록 보기
2/4
post-thumbnail

문제 설명

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

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

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

제한사항

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

입출력 예

genresplaysreturn
["classic", "pop", "classic", "classic", "pop"][500, 600, 150, 800, 2500][4, 1, 3, 0]

문제풀이

먼저 전달인자로 들어온 장르배열과 재생 횟수의 배열을 원하는 해시테이블 형태로 변형을 해야겠다고 생각을 했다!

     const obj = {
         "classic" : {
             items : [{index : 0, plays : 500}, {index : 2 , plays :150}, {index : 3, plays : 800}],
             totalPlays : 3100,
         },
         "pop" : {
             ... : ...
             ... : ...
         }
     }

따라서 genres 배열을 map을 통해 루프를 돌려줬는데, 입출력 예시를 보면 리턴값으로 인덱스 배열을 전달해줘야 되기 때문에 map 메서드의 콜백함수에서 currentValue와 currentIndex를 받아와서 처리를 해주었다.
여기서 장르배열은 중복된 값이 허용되기 때문에 그에 따른 분기처리를 추가적으로 해주었다.

const songs = {};
genres.map((genre,index) => {
  // 키 존재유무(최초 삽입이 아닌 경우)
  if (Object.keys(songs).includes(genre)) {
    songs[genre].items.push({index : index, plays : plays[index]});
    songs[genre].totalPlays += plays[index]
  } else {
    // 키가 없을 때(최초 삽입)
    songs[genre] = {
      items : [
        {
          index : index,
          plays : plays[index]
        }
      ],
      totalPlays : plays[index]
    }
  }
})

위와 같이 map 메소드를 돌려주면 songs는 obj 형태로 정렬이 이루어진다.

다시 문제를 천천히 읽어보면 코딩하면서 필요한 조건들은 다음과 같다.

  1. 가장 많이 재생된 장르
  2. 장르 내에서 많이 재생된 노래 2곡
  3. 장르 내 재생횟수가 같을 경우 index가 빠른 순
  4. 모든 장르는 재생된 횟수가 다름
  5. 장르 내 곡이 한 곡뿐이라면 한 곡만 리턴

따라서 songs 객체에 정리해둔 totalPlays를 정렬해야겠다고 생각했고,
totalPlays 라는 이름으로 배열을 새로 만들어 준 뒤에
songs 객체에서 totalPlays의 value를 totalPlays 배열에 넣어주었다.

const totalPlays = [];
for(const key in songs) {
  totalPlays.push(songs[key].totalPlays);
}

위의 로직을 통해 모든 장르들의 재생 횟수의 합이 배열 형태로 변형되었고, 아직은 재생 횟수가 많은 순서대로 정렬되어있지 않기 때문에, sort 메소드를 통해 정렬을 해주었다.

totalPlays.sort((a, b) => {return b - a});

이제 모든 재생횟수를 큰 순서대로 정렬했다면, 값과 매칭되는 장르별로 정렬을 해줄 필요가 있다. 따라서 sortedGenres라는 배열을 만든 뒤에 totalPlays와 맨 처음 만들어 놓은 songs 객체와 이중 for문 형태로 비교 후 매칭되는 장르를 sortedGenres 배열에 push 해주었다!

const sortedGenres = [];
totalPlays.map(plays => {
  for (const key in songs) {
    if (songs[key].totalPlays === plays) {
      sortedGenres.push(key)
    }
  }
})

이제 어떤 장르가 가장 많이 재생되었는지 알 수 있게 되었다. 4번의 조건을 보면 모든 장르는 재생된 횟수가 다르기 때문에 따로 조건문을 작성해주지 않아도 된다.
신경써야할 것은 2번과 3번, 5번 기준뿐이다!
정렬해둔 sortedGenres 배열을 map 메소드를 통해 다시 루프를 돌아줄 것이다.
배열의 각 value값을 받아와서 songs객체의 키로 조회를 하면 items 배열을 얻을 수 있다.
그 다음 해당 배열을 플레이 순서대로 정렬하면 2번의 기준을 해결할 수 있다. 마지막으로 장르 내에 플레이된 순으로 정렬된 배열을 3번과 5번 기준으로 분기처리를 하면 모든 준비는 끝이 난다.

const sortedItems = sortedGenres.map(genre => {
  const items = songs[genre].items;
  const returnItems = [];
  items.sort((a, b) => {return b.plays - a.plays});
  // 아이템이 하나가 아닌 경우 정렬 후 리턴
  if (items.length !== 1) {
    // 플레이 횟수가 동일하고, 첫 번째 곡의 index가 두 번째 곡의 index보다 큰 경우
    if (items[0].plays === items[1].plays && items[0].index > items[1].index) {
      returnItems.push(items[1].index)
      returnItems.push(items[0].index)
    } else {
      returnItems.push(items[0].index)
      returnItems.push(items[1].index)
    }
    return returnItems;
  } else {
    //아이템이 하나인 경우 그냥 리턴
    returnItems.push(items[0].index);
    return returnItems;
  }
})

위와 같은 논리를 통과하고 나면 sortedItems라는 배열은 2차원 배열의 형태가 된다.
테스트 케이스를 기준으로 하면 [[4,1],[3,0]]이다!
이제 정말 끝이 났다!
sortedItems를 이중 for문을 돌아서 answer 배열에 push한 뒤에 리턴해주면 모든 케이스를 통과할 수 있다!

느낀점

생각보다 풀기 까다로운 문제였던 것 같다..! 아직 알고리즘을 처음 배우는 나에게는 꽤나 오랜 시간이 걸렸다. 또한 고등학교 때 수학문제를 풀 때와 비슷하게 모든 정답은 문제에 나와있다!
문제를 꼼꼼히 읽는 습관을 들여야겠다!

-ps
다들 쉽게 푸셨겠지만 혹시나 어려움을 겪으신 분들이 있으시면 문제를 다시 한 번 차근차근 읽어보시길 바랍니다!

profile
천천히 한 걸음씩

0개의 댓글