[Hash] 베스트앨범

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

https://programmers.co.kr/learn/courses/30/parts/12077

 

 

package com.company;

import java.util.*;
public class Main {

    public static void main(String[] args) {
   // write your code here

        String[] genres ={"classic", "pop", "classic", "classic", "pop"};
        int[] plays ={500, 600, 150, 800, 2500};

        Map<String, Integer> gMap = new HashMap<>();
        Map<String, List> sMap = new HashMap<>();

        //장르값 입력
        for(int i=0; i<genres.length; i++){
            Song song = new Song(i, plays[i]);

                //장르
                gMap.put(genres[i], gMap.getOrDefault(genres[i], 0)+plays[i] );

                //Hash는 각 장르당 value로 음악리스트를 가짐
                List songList = sMap.getOrDefault(genres[i], new ArrayList());
                songList.add( song );
                sMap.put(genres[i], songList);
        }

        //장르순위대로 정렬
        List<String> gList = sortByValue(gMap);


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

        //각 장르 안에서 재생순서대로 정렬
        for(int i=0; i<gList.size(); i++){

            //현재장르
            System.out.println("[" + gList.get(i) + "]");
            List sList = sMap.get( gList.get(i) );
            Collections.sort(sList);

            for(int j=0; j<2; j++){//2개만 뽑는다
                Song song = (Song)sList.get(j);
                System.out.println(song.index + "/" + song.play);
                answerList.add(song.index);
                if(sList.size()==1) break; //1개뿐인 경우
            }
        }//for(i)


        int[] answerArray = new int[answerList.size()];
        for(int i=0; i<answerList.size(); i++){
            answerArray[i] = answerList.get(i);
        }


        for(int i=0; i<answerList.size(); i++){
            System.out.println(answerArray[i]);
        }
    }


    public static List sortByValue(final Map<String, Integer> map) {

        List<String> list = new ArrayList();
        list.addAll(map.keySet());

        Collections.sort(list,new Comparator<>() {
            public int compare(String key1, String key2) {
                if ( map.get(key1) > map.get(key2) ) return -1;
                else if ( map.get(key1) == map.get(key2) ) return 0;
                else return 1;
            }
        });

        return list;
    }


    static class Song implements Comparable<Song>{
        int index;
        int play;

        public Song(int index, int play) {
            this.index = index;
            this.play = play;
        }

        @Override
        public int compareTo(Song song) {
            if(this.play > song.play) return -1;
            if(this.play==song.play) return 0;
            return 1;
        }
    }
}

 

*장르순위 구할때(다른사람 소스에서 사용한 방법)

-gMap Key와 Value를 바꾼 후, Key로 sort하고 value를 가져오면 된다.

-생각해보니 확률은 낮겠지만, value값이 같아버리면 오류가 발생. (바꿨을 때 Key값이 중복되니까)

 

 

*전체적으로 HashMap의 Value를 Sort하면서 풀이

-다른사람들 소스를 보니 PriortyQueue를 쓴 것도 있음.

 

public static List sortByValue(final Map<String, Integer> map) {

        List<String> list = new ArrayList();
        list.addAll(map.keySet());

        Collections.sort(list,new Comparator<>() {
            public int compare(String key1, String key2) {
                if ( map.get(key1) > map.get(key2) ) return -1;
                else if ( map.get(key1) == map.get(key2) ) return 0;
                else return 1;
            }
        });

        return list;
    }

위 소스는 compareTo랑 비슷하게 만드려고 개조한것. 

이렇게짜면  하면 부등호 방향 하나만 바꿔주면 오름차순, 내림차순 바뀐다.

오름차순(>), 내림차순(<).

아래의 소스 모두 같은 의미이다.

 

 

Collections.sort(list,new Comparator() {
    public int compare(Object o1,Object o2) {
        Object v1 = map.get(o1);
        Object v2 = map.get(o2);
        return ((Comparable) v2).compareTo(v1);
    }
});

원본1 (http://ithub.tistory.com/34)

 

public int compare(Object keyA, Object keyB) {
    Comparable valueA = (Comparable) map.get(keyA);
    Comparable valueB = (Comparable) map.get(keyB);
    return valueB.compareTo(valueA);
}

원본2

 

Collections.sort(list,new Comparator<Object>() {
    public int compare(Object key1, Object key2) {
        Comparable value1 = map.get(key1);
        Comparable value2 = map.get(key2);
        return value2.compareTo(value1);
    }
});

중간과정

 

 

 

 

2022. 7. 27

Compartor안쓰고 Comparable만 사용한 방법

import java.util.*;

class Solution {
    
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

    private Map<String, PriorityQueue<Music>> musicHash = new HashMap<>();
    private Map<String, Genre> genreHash = new HashMap<>();
    
    public int[] solution(String[] genres, int[] plays) {

        for(int i=0; i<genres.length; i++) {
            String genreTitle = genres[i];
            
            PriorityQueue<Music> mPq = musicHash.getOrDefault(genreTitle, new PriorityQueue<Music>());
            Music music = new Music(i, plays[i]);
            mPq.add(music);
            musicHash.put(genreTitle, mPq);
            
            Genre genre = genreHash.getOrDefault(genreTitle, new Genre(genreTitle));
            genre.playCountSum += plays[i];
            genreHash.put(genreTitle, genre);
        }

        List<Genre> genreList = new ArrayList<Genre>(genreHash.values());
        Collections.sort(genreList);

        List<Integer> answerList = new ArrayList<>();
        for(Genre genre : genreList) {
            PriorityQueue<Music> mPq = musicHash.get(genre.genreStr);

            answerList.add(mPq.poll().index);
            if(!mPq.isEmpty()) answerList.add(mPq.poll().index);
        }

        int ans[] = new int[answerList.size()];
        for(int i=0; i<answerList.size(); i++) {
            ans[i] = answerList.get(i);
        }

        return ans;
    }

    static class Music implements Comparable<Music> {
        int index;
        int playCount;

        public Music(int index, int playCount) {
            this.index = index;
            this.playCount = playCount;
        }

        @Override
        public int compareTo(Music m) {
            if(this.playCount > m.playCount) return -1;
            if(this.playCount < m.playCount) return 1;

            if(this.index < m.index) return -1;
            return 1;
        }
    }

    static class Genre implements Comparable<Genre> {
        String genreStr;
        int playCountSum;

        Genre(String genreStr) {
            this.genreStr = genreStr;
            this.playCountSum = 0;
        }

        @Override
        public int compareTo(Genre m) {
            if(this.playCountSum > m.playCountSum) return -1;
            return 1;
        }
    }
}