[프로그래머스 lev3/JS] 베스트앨범

문제 출처

프로그래머스 lev3 - 베스트앨범

나의 풀이

1차시도(86.7/100)

해시 문제이므로 객체로 정보를 저장하되, 2개의 객체를 만들었다.

• 순서가 필요하므로 []을 갖는 values 객체
• plays에 매칭되는 index도 필요하므로 {}를 갖는 keys 객체

plays[i]를 key 값으로 저장하면 중복이 발생하는 것 같다.

function solution(genres, plays) {
  let values = {}
  let keys = {}
  let answer = []

  for(let i=0; i<genres.length; i++){
    let genre = genres[i]
    // if(values[genre] === undefined){
    if(!values[genre]) values[genre] = []
    values[genre].push(plays[i])
  }
  for(let i=0; i<genres.length; i++){
    let genre = genres[i]
    // if(values[genre] === undefined){
    if(!keys[genre]) keys[genre] = {}
    keys[genre][plays[i]] = i
  }
  // console.log(values)
  // console.log(keys)
  let tmp = {}

  for(let genre of Object.keys(values)){
    values[genre].sort((a,b) => b-a)
    // console.log(values[genre])
    let tray = []
    let sum = 0

    for(let plays of values[genre]){
      sum += Number(plays)
      if(tray.length < 2) tray.push(keys[genre][plays])
    }
    // console.log(tray, sum)
    tmp[sum] = [...tray]
    answer.push(sum)
  }
  // console.log(tmp)

  answer.sort((a,b) => b-a)
  for(let i=0; i<answer.length; i++){
    let item = answer[i]
    answer[i] = tmp[item]
  }
  return [].concat(...answer)
}

console.log(
  solution(
    ["classic", "pop", "classic", "classic", "pop"],
    [500, 600, 150, 800, 2500]
  )
); // [4, 1, 3, 0]

2차시도 (통과)

하지만 너무 더럽게 풀었다...

반례는 같은 장르 안에서 plays 값이 똑같아서 값이 제대로 저장되지 않는 경우이다. 이를 막기 위해, keys 객체를 만들 때 keys[genre][plays[i]] = i;가 아니라 keys[genre][i] = plays[i];를 사용해서 index로 값을 저장한다.

그리고 나서 for..of문을 순회한다.

• 순회하는 동안 tray에 각 장르들의 plays 합을 구해서 sum 변수에 저장한다. 나중에 이 sum을 사용해서 순서를 찾을 것이다.
• 순회하는 동안 res 배열에는 가장 큰 plays들의 index 정보들을 저장한다.
• 순회하는 동안 count를 사용해 장르 내 곡이 2개 이상이면 while문을 사용해 2개를 강제하지만, 2개 이상이 아닐 경우에는 1개만 찾아서 res 배열을 완성하도록 한다.

res 배열을 temp라는 객체에 저장하고
answer 배열에는 sum을 넣는다.
sum으로 순서를 맞춘 뒤에, answer 배열의 각 요소에 들어간 sum에 맞는 res 배열을 불러온 뒤, 배열을 벗겨서 정답을 반환한다.

참고로 이때 array.flat() 보다는 [].concat(...array)가 더 빠르다고 한다. (V8 브라우저 엔진에서는 아직 flat이 최적화되지 않았기 때문)
[Javascript] Array.flat() 은 느리다.

function solution(genres, plays) {
  let values = {};
  let keys = {};
  let answer = [];
  let temp = {}

  for (let i = 0; i < genres.length; i++) {
    let genre = genres[i];
    // if(values[genre] === undefined){
    if (!values[genre]) values[genre] = [];
    values[genre].push(plays[i]);
  }
  for (let i = 0; i < genres.length; i++) {
    let genre = genres[i];
    // if(values[genre] === undefined){
    if (!keys[genre]) keys[genre] = {};
    // keys[genre][plays[i]] = i;
    keys[genre][i] = plays[i];
  }
  // console.log(values)
  // console.log(keys)

  for(let genre of Object.keys(keys)){
    let res = []
    let tray = new Array(genres.length).fill(0)
    let count = 0
    for(let idx of Object.keys(keys[genre])){
      tray[idx] = Number(keys[genre][idx])
      if(tray[idx]) count++
    }
    let sum = tray.reduce((a, b) => a + b)
    // console.log(tray, count)

    if(count >= 2) {
      while(res.length < 2){
        let max = Math.max(...tray)
        let target = tray.indexOf(max)
        tray[target] = -1
        res.push(target)
      }
    }
    else if(count < 2) {
      let max = Math.max(...tray)
      let target = tray.indexOf(max)
      tray[target] = -1
      res.push(target)
    }
    // console.log(res, sum)
    temp[sum] = [...res]
    answer.push(sum)
  }

  answer.sort((a, b) => b - a)

  for(let i=0; i<answer.length; i++){
    let item = answer[i]
    answer[i] = temp[item]
  }

  return [].concat(...answer)  
}

console.log(
  solution(
    ["classic", "pop", "classic", "classic", "pop"],
    [800, 600, 150, 800, 2500]
  )
); // [4, 1, 0, 3]

다른 풀이 1

function solution(genres, plays) {
  var dic = {};
  genres.forEach((t,i)=> {
      dic[t] = dic[t] ?  dic[t] + plays[i] : plays[i];        
  });

  var dupDic = {};
  return genres          
        .map((t,i)=> ({genre : t, count : plays[i] , index : i}))
        .sort((a,b)=>{               
            if(a.genre !== b.genre) return dic[b.genre] - dic[a.genre];
            if(a.count !== b.count) return b.count - a.count;
            return a.index - b.index;
         })
        .filter(t=>  {
            if(dupDic[t.genre] >= 2) return false;
            dupDic[t.genre] = dupDic[t.genre] ? dupDic[t.genre]+ 1 : 1;
            return true;
          })
        .map(t=> t.index);    
}

다른 풀이 2

function solution(genres, plays) {
    const count = {};
    let answer = [];
    const acc = genres.reduce((a, c, i) => {
        debugger;
        count[c] ? count[c].push([i, plays[i]]) : count[c] = [[i, plays[i]]];
        return a.set(c, a.get(c) ? a.get(c) + plays[i] : plays[i]), a;
    }, new Map());

    [...acc].sort((a, b) => b[1] - a[1]).map(v => {
            answer = answer.concat(count[v[0]].sort((c, d)=>d[1]-c[1]).slice(0,2));
    });
    return answer.map(v=>v[0]);
}

다른 풀이 3

function solution(genres, plays) {
    var songs = 
        genres.map((genre, index) => {
            return {
                no: index,
                genre: genre,
                playCount: plays[index]    
            };
        });

    var genrePlayCount = [];
    songs.forEach(song => {
        var thisGenre = genrePlayCount.find(genrePlay => genrePlay.genre === song.genre);
        if (!thisGenre) {
            genrePlayCount.push({
                genre: song.genre, totalPlayCount: song.playCount
            });
        } else {
            thisGenre.totalPlayCount += song.playCount;
        }
    });

    genrePlayCount.sort((a, b) => b.totalPlayCount - a.totalPlayCount);

    var answer = [];
    genrePlayCount.forEach(genrePlay => {
        var thisGenreSongs = songs.filter(song => genrePlay.genre === song.genre);
        thisGenreSongs.sort((a, b) => b.playCount - a.playCount);
        answer.push(thisGenreSongs[0].no);
        if (thisGenreSongs.length > 1) {
            answer.push(thisGenreSongs[1].no);
        }
    });

    return answer;
}

참고

[Javascript] Array.flat() 은 느리다.