Programmers[42579] - 베스트앨범[Level2]

링크

프로그래머스

문제설명

• 장르는 합계빈도수로 정렬하고
• 장르별 상위2개 빈도수의 노래 index를 저장

문제풀이

• 장르별 sum을 기준으로 정렬
• 장르 내 리스트들을 가격들을 기준으로 고유번호 정렬
• 자료구조 {KEY = 장르, VALUE = {list{idx, value}, sum value}}

문제코드

package programmers;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Solution42579_베스트앨범 {

    static class Comp implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o2[1]-o1[1];
        }
    }

    public static Comp comp = new Comp();


    static class Music{
        private int sum;
        private PriorityQueue<int[]> pq;

        public int getSum() {
            return sum;
        }

        public void setSum(int sum) {
            this.sum = sum;
        }

        public PriorityQueue<int[]> getPq() {
            return pq;
        }

        public void setPq(PriorityQueue<int[]> pq) {
            this.pq = pq;
        }

        public Music() {
            this.sum = 0;
            this.pq = new PriorityQueue<int[]>(comp);
        }


        public Music(int sum) {
            this.sum = sum;
            this.pq = new PriorityQueue<int[]>(comp);
        }
    }


    public static int[] solution(String[] genres, int[] plays) {
        HashMap<String, Music> hm = new HashMap<String, Music>();

        int len = genres.length;

        for (int i = 0; i < len; i++) {
            hm.put(genres[i], new Music());
        }

        for (int i = 0; i < len; i++) {
            hm.get(genres[i]).getPq().add(new int[] {i,plays[i]});
            hm.get(genres[i]).setSum((hm.get(genres[i]).getSum()+plays[i]));
        }

        LinkedList<String> keylist = new LinkedList<String>(hm.keySet());
        keylist.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return hm.get(o2).getSum() - hm.get(o1).getSum();
            }
        });

        LinkedList<Integer> anslist = new LinkedList<Integer>();

        for (String type : keylist) {
            for (int j = 0; j < 2; j++) {
                PriorityQueue<int[]> tpq = hm.get(type).getPq();
                if(!tpq.isEmpty()) {
                    anslist.add(tpq.poll()[0]);
                }
            }
        }

//        Integer[] ans = anslist.toArray(new Integer[0]);
        int[] ans = new int[anslist.size()];
        for (int i = 0; i < anslist.size(); i++) {
            ans[i] = anslist.get(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new String[] {"classic", "pop", "classic", "classic", "pop"},
                                    new int[] {500, 600, 150, 800, 2500})));
    }
}

아쉬운점

• 자료구조 구현이 미숙했음

  • 시간 겁나 오래걸림
  • TreeSet을 이용해서 장르별로 정렬해보려 했음
    • TreeSet을 이용하면 Key 기준으로 쉽게 정렬할 수 있으나, Value로 정렬해주는 컬렉션은 존재하지 않는다.
    • 즉 정렬하려면 KeySet를 받아서 Value를 접근하면서 정렬해야하는데 이럴거면 TreeSet이아니라 HashSet사용하는게 낫다.
    • HashSet을 Value로 정렬해주는 방법 몰라서 헤맸음
    • KeyList 뽑아서 KeyList를 Value쌍을 기준으로 정렬한다.
    • KeyList가 Iterator가 되고, Iterator를 정렬하는 셈

•  

• 오류? 버그?

  • comparator o2[0]-o1[0]으로 하면 o[1] 기준으로 정렬함...
  • comparator o2[1]-o1[1]으로 하면 o[0] 기준으로 정렬함...
    • 근데 또 하다보니 제대로 정상작동함 왜지?
  • Static class Comp를 이용해서 comparator 선언했는데 정렬이 잘 안됬었음
    • 근데 또 하다보니 제대로 정상작동함 왜지?

잘한점

• 포기하지 않고 자료구조 공부를 해서 풀었다

참고

• HashMap자료구조를 반복, 탐색하는 방법이 정리되어있다.

  • https://fullstatck.tistory.com/10