오랜만에 알고리즘을 한번 풀어봤다. 그래도 나름 자바스크립트로 6개월을 넘게 개발했다고, 자바는 많이 잊어버렸다. 자바스크립트로는 금방 풀이를 떠올릴 수 있었는데, 타입의 제한 때문인지 자바로는 풀기 어려웠다.

먼저 문제를 읽고, 이 문제를 풀기 위해 필요한 값을 정리해봤다.

  • 장르별 총 곡 재생 수
  • 장르 내에서 가장 많이 재생된 2개 곡의 인덱스 값 (장르 내의 곡이 1개일 경우 1개)

{장르}:{장르의 총 재생 수}로 매칭하여 계산하기 편하기 때문에, Hash 카테고리로 분류된 것 같다. 그런데 단순히 장르의 총 재생 수만 필요한 것이 아니라, 그 안에서 가장 많이 재생된 2개 곡의 인덱스도 필요하다.

그래서 저장할 Value를 원시 타입으로 저장하는 것이 아니라, {장르의 총 재생 수, 해당 장르에서 재생된 곡 인덱스/재생 수}의 형태로 새로운 클래스를 만들어서 저장해보기로 했다.

풀이

위에 설명한 형태를 자바스크립트의 객체 형태로 보자면, 아래와 같이 정보를 저장한다.

genreList = {
    classic: {
        totalPlay: 1450,
        playList: [[0, 500], [2, 150], [3, 800]],
    },
    pop: {
        totalPlay: 3100,
        playList: [[1, 600], [4, 2500]],
    },
}

이렇게 정리된 정보를 바탕으로 genreList순, genre별 playList의 재생 순으로 정렬한 뒤 값을 가져오면 된다.

사실 효율성을 좋게 개발하려고 하면 이 부분이 제일 난해하다. 일단 장르 정렬을 위해서 한번 전체 순회를 하는데, 이 때 장르 내부도 함께 정렬이 되면 좋겠지만 그 부분까진 방법이 떠오르지 않아서 구현하지 못했다.

장르를 정렬한 다음엔, 장르 내부에서 가장 많이 재생된 순서의 곡 2개를 정렬한다. 장르를 정렬한 것과 동일하게 전체 순회를 돌아서 정렬했다. (하지만 이 부분은 최댓값 2개만 찾으면 되기 때문에 버블 정렬로 두개만 찾아내는 것이 더 나을 것 같다)

코드

JAVA

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.Collections;
import java.util.Comparator;

class Genre {
    public int totalPlay;
    public List<int[]> playList = new ArrayList<>();

    public Genre(int playCount, int[] playList) {
        this.totalPlay = playCount;
        this.playList.add(playList);
    }

    public void increaseTotalPlay(int playCount) {
        this.totalPlay += playCount;
    }

    public void addPlayList(int[] playList) {
        this.playList.add(playList);
    }
}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Genre> genreSummary = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            Genre genre = genreSummary.get(genres[i]);
            if (genre == null) {
                genreSummary.put(genres[i], new Genre(plays[i], new int[] { i, plays[i] }));
            } else {
                genre.increaseTotalPlay(plays[i]);
                genre.addPlayList(new int[] { i, plays[i] });
            }
        }

        List<Genre> genreList = new ArrayList(genreSummary.values());

        Collections.sort(genreList, new Comparator<Genre>() {
            public int compare(Genre genre1, Genre genre2) {
                return genre2.totalPlay - genre1.totalPlay;
            }
        });

        List<Integer> answer = new ArrayList<>();

        for (int i = 0; i < genreList.size(); i++) {
            Genre genre = genreList.get(i);

            Collections.sort(genre.playList, new Comparator<int[]>() {
                public int compare(int[] play1, int[] play2) {
                    return play2[1] - play1[1];
                }
            });

            answer.add(genre.playList.get(0)[0]);

            if (genre.playList.size() > 1) {
                answer.add(genre.playList.get(1)[0]);
            }
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

}

JavaScript

function solution(genres, plays) {
  const summaryGenres = genres.reduce((acc, cur, index) => {
    if (!acc[cur]) {
      acc[cur] = {
        totalPlay: 0,
        playList: [],
      };
    }

    acc[cur].totalPlay += plays[index];
    acc[cur].playList.push([index, plays[index]]);

    return acc;
  }, {});

  const summaryGenresList = Object.values(summaryGenres).sort(
    (genre1, genre2) => {
      return genre2.totalPlay - genre1.totalPlay;
    },
  );

  const answer = summaryGenresList.reduce((acc, genre) => {
    genre.playList.sort((play1, play2) => {
      return play2[1] - play1[1];
    });

    acc.push(genre.playList[0][0]);

    if (genre.playList.length > 1) {
      acc.push(genre.playList[1][0]);
    }

    return acc;
  }, []);

  return answer;
}