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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제 풀이

• 자료구조와 정렬을 이용하여 풀이하였다.
• 크게 아래 2단계로 이뤄진다.

  1. Map<장르명, 총재생수>, Map<장르명, List<곡정보>> 2개의 장르별 곡정보를 만든다.
  2. Map<장르명, 총재생수>에서 원소를 하나씩 빼며 우선 순위큐로 정렬시켜준다.
     이후 해당 장르명에 해당하는 List<곡정보>를 정렬하여 상위 1개 및 2개씩 빼주며 번호를 확인한다.

• 자세한 내용은 소스를 참고하면된다.

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public class Song implements Comparable<Song> {
        int num;
        int count;

        public Song(int num, int count) {
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(Song o) {
            if (this.count < o.count) return 1;
            else if (this.count > o.count) return -1;
            else {
                if (this.num > o.num) return 1;
                else return -1;
            }
        }
    }

    public class Genre implements Comparable<Genre> {
        String name;
        int count;

        public Genre(String name, int count) {
            this.name = name;
            this.count = count;
        }

        @Override
        public int compareTo(Genre o) {
            if (this.count < o.count) return 1;
            else return -1;
        }
    }
    public int[] solution(String[] genres, int[] plays) {
        //입력
        Map<String, Integer> genreIn = new HashMap<>();
        Map<String, List<Song>> songIn = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            String name = genres[i];
            int count = plays[i];
            if (genreIn.containsKey(name)) genreIn.put(name, genreIn.get(name) + count);
            else genreIn.put(name, count);
            if (songIn.containsKey(name)) songIn.get(name).add(new Song(i, count));
            else songIn.put(name, new ArrayList<>(Collections.singletonList(new Song(i, count))));
        }

        //출력
        List<Integer> result = new ArrayList<>();
        PriorityQueue<Genre> q = new PriorityQueue<>();
        for (String key : genreIn.keySet()) {
            q.add(new Genre(key, genreIn.get(key)));
        }
        while(!q.isEmpty()) {
            Genre cur = q.poll();
            List<Song> songList = songIn.get(cur.name);
            Collections.sort(songList);
            if (songList.size() == 1)
                result.add(songList.get(0).num);
            else {
                result.add(songList.get(0).num);
                result.add(songList.get(1).num);
            }
        }
        int[] print = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            print[i] = result.get(i);
        }
        return print;
    }
}