Algo - HashMap과 Comparator(베스트앨범)

hyekyeong Song·2020년 7월 15일
Javaalgorithm
0

Algorithm

목록 보기
10/10
  • 문제 출처 : 프로그래머스
  • 문제명 : 베스트앨범
  • 분류 : Hash
  • 언어 : Java
  • 체감 난이도 : ⭐⭐⭐⭐⭐
  • 풀이 시간 : 50min
  • Fail Cnt : 0

1. 문제 접근 방법

문제의 조건에 따르면 노래를 재생 할 때, (가장 많이 재생한 장르) > (장르 내 많이 재생한 장르(if 재생 횟수가 동일할 경우 고유번호가 낮은 순으로 정렬)) 에 따라 곡을 수록해야한다.

1)자료구조와 사용자 정의 클래스

(1) 장르별 플레이된 카운트를 저장하는 HashMap

HashMap<String, Integer> genresPlayCnt = new HashMap<String, Integer>();

(2) 곡의 고유번호와 재생횟수를 저장하는 Music 사용자 정의 객체

!!음악 재생 횟수가 많을수록 우선순위가 높으며, 재생 횟수가 동일할 경우 고유번호가 낮은 순으로 정렬하도록 Comparable 인터페이스를 구현한다

    public class Music implements Comparable<Music>{
        int uniqNum;    //고유번호
        int plays;  //재생횟수

        public Music (int uniqNum, int plays) {
            this.uniqNum = uniqNum;
            this.plays = plays;
        }

        @Override
        public int compareTo(Music music) { //음악 재생횟수가 많은것을 앞에 위치
            if(this.plays < music.plays) { return 1;}
            else if(this.plays > music.plays) { return -1;}
            else {
                if(this.uniqNum > music.uniqNum) { return 1; }
                else if(this.uniqNum == music.uniqNum) { return 0; }
                else { return  -1; }
            }
        }
    }

(3) 장르별로 노래 리스트를 저장하는 HashMap

HashMap<String, ArrayList<Music>> musicList = new HashMap<String, ArrayList<Music>>();

2. Comparator 인터페이스

위와같이 자료구조를 HashMap으로 설계하고 값을 정렬해야할 경우, 이는 Comparator 인터페이스를 구현하여 수행할 수 있다.

1) Map 객체에 저장된 전체 객체를 가져오고 싶을 때

  • 모든 키를 가져오고 싶을 경우 : keySet() 메소드를 사용해 모든 키를 Set 컬렉션으로 가져온다 -> Iterator를 통해 키를 얻고 이때 값은 get()메소드로 얻으면 된다.
  • 모든 (키, 값) 쌍을 가져오고 싶을 경우 : entrySet() 메소드로 모든 Map.Entry를 Set 컬렉션으로 가져온다 -> Iterator를 통해 getKey()와 getValue()메소드를 통해 키와 값을 얻는다.

2) Comparable과 Comparator

Comparable은 이전에 게시물을 통해 사용예시를 바탕으로 설명한 적 있다.
Comparable의 설명과 사용방법 링크

(1) Comparable

: Comparable은 compareTo()메소드를 오버라이딩해, 정렬의 기준을 만들어 오름차순 또는 내림차순으로 정렬할 수 있다.

(2) Comparator

: Comparator는 객체간 특정한 기준에 따라 정렬하고 싶을 때 사용하거나, Comparable의 구현 없이 객체를 정렬하고 싶을 때 사용한다. 정렬의 기준은 compare(Object ob1, Object ob2)메소드의 구현을 통해 정할 수 있다.

리턴타입메소드
intcompare(T o1, T o2)
  • o1이 o2보다 앞에 오게 하려면 음수 리턴
  • o2가 o1보다 앞에 오게 하려면 양수 리턴
  • 두 값이 동등하면 0 리턴

3. 코드로 확인하는 Comparator 정렬

1) 자료구조에 데이터를 저장하는 코드

HashMap을 정렬하기 전에 먼저 데이터를 각 변수에 저장하자

        HashMap<String, Integer> genresPlayCnt = new HashMap<String, Integer>();    //장르별로 플레이된 카운트 저장
        HashMap<String, ArrayList<Music>> musicList = new HashMap<String, ArrayList<Music>>();  //장르별 노래 저장


        for(int i=0; i<genres.length; i++) {
            if(genresPlayCnt.containsKey(genres[i])) {
                genresPlayCnt.put(genres[i], (genresPlayCnt.get(genres[i]) + plays[i]));   //재생횟수 더해주기
            } else {    //새로운 값 넣어주기
                genresPlayCnt.put(genres[i], new Integer(plays[i]));
                //hashMap생성
                musicList.put(genres[i], new ArrayList<Music>());
            }
            //장르에 따른 Music객체 생성해서 넣기
            ArrayList<Music> tempMusicList = musicList.get(genres[i]);
            tempMusicList.add(new Music(i, plays[i]));
            musicList.put(genres[i], tempMusicList);
        }

예시)

  • Input :
genresplays
[classic, pop, classic, classic, pop][500, 600, 150, 800, 2500]
  • 위의 코드 실행 이후 자료구조
    (1) genresPlayCnt
KeyValue
"classic"1450
"pop"3100

(2) musicList

KeyValue
"classic"(0, 500), (2, 150), (3, 800)
"pop"(1, 600), (4, 2500)

2) genresPlayCnt를 Comparator를 사용해 내림차순 정렬하는 코드

        //genresPlayCnt를 value로 정렬하기(내림차순)
        //Map.Entry리스트를 생성한다
        List<Map.Entry<String, Integer>> entries = new ArrayList<Map.Entry<String, Integer>>(genresPlayCnt.entrySet());
        //Comparator를 사용해 내림차순으로 정렬한다
        Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> obj1, Map.Entry<String, Integer> obj2) {
                if(obj1.getValue() < obj2.getValue()) return 1;
                else if(obj1.getValue() == obj2.getValue()) return 0;
                else return -1;
            }       
        });

위의 public int compare() 메소드는 아래와 같이 더 간단하게 작성할 수 있다.

            public int compare(Map.Entry<String, Integer> obj1, Map.Entry<String, Integer> obj2) {
		return obj2.getValue().compareTo(obj1.getValue());
            }

3) 내림차순으로 정렬된 entries의 값을 가져와서 장르에 해당하는 Music 객체 리스트를 정렬(+곡을 수록)하는 코드

        ArrayList<Integer> tempAnswer = new ArrayList<Integer>();   //수록할 곡의 고유번호를 저장한다
        String musicGenre = "";
        
        for(Map.Entry<String, Integer> entry : entries) {
            musicGenre = entry.getKey();    //장르 알아내서
            
            ArrayList<Music> sortMusicList = musicList.get(musicGenre); //장르에 해당하는 Music List가져오고
            Collections.sort(sortMusicList);    //정렬한다
            //최대 두 곡을 수록한다
            if(sortMusicList.size() < 2) {
                for(int i=0; i<sortMusicList.size(); i++) {
                    tempAnswer.add(sortMusicList.get(i).uniqNum);
                }
            } else {
                for(int i=0; i<2; i++) {
                    tempAnswer.add(sortMusicList.get(i).uniqNum);
                }
            }
        }

4) 전체 코드

import java.util.*;

class Solution {
    public class Music implements Comparable<Music>{
        int uniqNum;    //고유번호
        int plays;  //재생횟수

        public Music (int uniqNum, int plays) {
            this.uniqNum = uniqNum;
            this.plays = plays;
        }

        @Override
        public int compareTo(Music music) { //음악 재생횟수가 많은것을 앞에 위치
            if(this.plays < music.plays) { return 1;}
            else if(this.plays > music.plays) { return -1;}
            else {
                if(this.uniqNum > music.uniqNum) { return 1; }
                else if(this.uniqNum == music.uniqNum) { return 0; }
                else { return  -1; }
            }
        }
    }

    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        HashMap<String, Integer> genresPlayCnt = new HashMap<String, Integer>();    //장르별로 플레이된 카운트 저장
        HashMap<String, ArrayList<Music>> musicList = new HashMap<String, ArrayList<Music>>();  //장르별 노래 저장


        for(int i=0; i<genres.length; i++) {
            if(genresPlayCnt.containsKey(genres[i])) {
                genresPlayCnt.put(genres[i], (genresPlayCnt.get(genres[i]) + plays[i]));   //재생횟수 더해주기
            } else {    //새로운 값 넣어주기
                genresPlayCnt.put(genres[i], new Integer(plays[i]));
                //hashMap생성
                musicList.put(genres[i], new ArrayList<Music>());
            }
            //장르에 따른 Music객체 생성해서 넣기
            ArrayList<Music> tempMusicList = musicList.get(genres[i]);
            tempMusicList.add(new Music(i, plays[i]));
            musicList.put(genres[i], tempMusicList);
        }

        //genresPlayCnt를 value로 정렬하기(내림차순)
        List<Map.Entry<String, Integer>> entries = new ArrayList<Map.Entry<String, Integer>>(genresPlayCnt.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> obj1, Map.Entry<String, Integer> obj2) {
                if(obj1.getValue() < obj2.getValue()) return 1;
                else if(obj1.getValue() == obj2.getValue()) return 0;
                else return -1;
            }       
        });

        ArrayList<Integer> tempAnswer = new ArrayList<Integer>();   //answer값 임시 저장
        String musicGenre = "";
        for(Map.Entry<String, Integer> entry : entries) {
            musicGenre = entry.getKey();    //장르 알아내서
            ArrayList<Music> sortMusicList = musicList.get(musicGenre); //장르에 해당하는 Music List가져오고
            Collections.sort(sortMusicList);    //정렬한다
            //최대 두 곡을 수록한다
            if(sortMusicList.size() < 2) {
                for(int i=0; i<sortMusicList.size(); i++) {
                    tempAnswer.add(sortMusicList.get(i).uniqNum);
                }
            } else {
                for(int i=0; i<2; i++) {
                    tempAnswer.add(sortMusicList.get(i).uniqNum);
                }
            }
        }
        
        answer = new int[tempAnswer.size()];
        for(int i=0; i<tempAnswer.size(); i++) {
            answer[i] = tempAnswer.get(i);
        }

        return answer;
    }
}

참고
TreeSet과 TreeMap 자료구조는 키의 저장과 동시에 자동으로 오름차순으로 정렬되는데, 이때 정렬을 위해 java.lang.comparable을 구현한 객체를 요구한다. (Integer, Double, String,.. 은 모두 Comparable 인터페이스를 구현하고 있으므로 기본 정렬시 별도로 구현하지 않아도 된다)
즉, 사용자 정의 클래스도 Comparable을 구현하면 TreeSet과 TreeMap을 사용한 자동 정렬이 가능하다.

profile
hyekyeong Song
안녕하세요😀😀
이전 포스트

알고리즘 - 분할정복(점프와 순간 이동)

0개의 댓글