[프로그래머스]해시 : 베스트앨범 (level 3) (java)

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

코딩테스트 연습 - 베스트앨범 | 프로그래머스

 

 

방법1 : Comparable 활용

import java.util.*;
 
 
class Solution {
    public class Music implements Comparable<Music> {
 
        private int played;
        private String genre;
        private int index;
 
        public Music(String genre, int played, int index) {
            this.genre = genre;
            this.played = played;
            this.index = index;
        }
 
        @Override
        public int compareTo(Music other) {
            // 많이 재생된 장르를 먼저
            int iOrder = CountMap.get(other.genre) - CountMap.get(this.genre);
            if (iOrder != 0) {
                return iOrder;
            }
            // 많이 재생된 노래를 먼저
            if (iOrder == 0) {
                return other.played - this.played;
            }
            // 고유 번호가 낮은 노래를 먼저
            if (iOrder == 0) {
                return this.index - other.index;
            }
            return iOrder;
        }
    }
 
    Map<String, Integer> CountMap;
 
    public int[] solution(String[] genres, int[] plays) {
 
        CountMap = new HashMap<String, Integer>();
        List<Music> infoList = new ArrayList<Music>();
 
        // infoList : 노래 정보  
        // CountMap : 장르별 재생횟수 카운트
        for (int i = 0; i < genres.length; i++) {
 
            String genre = genres[i];
            int played = plays[i];
 
            Music music = new Music(genre, played, i);
            infoList.add(music);
 
            if (CountMap.containsKey(genre)) {
                CountMap.put(genre, CountMap.get(genre) + played);
                continue;
            }
            CountMap.put(genre, played);
        }
 
        // 주어진 조건대로 정렬
        Collections.sort(infoList);
 
        // 장르별 최대 2곡씩 선택
        return pickSongs(infoList);
    }
 
    private int[] pickSongs(List<Music> infoList) {
 
        int count = 1;
        for (int i = 1; i < infoList.size(); i++) {
            Music music1 = infoList.get(i);
            Music music2 = infoList.get(i - 1);
 
            if (count >= 2) {
                if (music1.genre.equals(music2.genre)) {
                    infoList.remove(i);
                    i--;
                    continue;
                }
                count = 0;
            }
            if (!music1.genre.equals(music2.genre)) {
                count = 1;
                continue;
            }
            if (count < 2) {
                count++;
            }
        }
 
        // 리스트 -> 배열
        int[] answer = new int[infoList.size()];
 
        for (int i = 0; i < answer.length; i++) {
            answer[i] = infoList.get(i).index;
        }
        return answer;
    }
}

 

방법2: Comparator 활용

import java.util.*;
import java.util.Map.Entry;
 
class Solution {
    public int[] solution(String[] genres, int[] plays) {
 
        Map<String, Integer> CountMap = new HashMap<String, Integer>();
        Map<Integer, Integer> playsMap = new HashMap<Integer, Integer>();
        
        // playsMap : plays 배열 -> 맵 
        // CountMap : 장르별 재생횟수 카운트 
        for (int i = 0; i < genres.length; i++) {
 
            String key = genres[i];
            playsMap.put(i, plays[i]);
 
            if (CountMap.containsKey(key)) {
                CountMap.put(key, CountMap.get(key) + plays[i]);
                continue;
            }
            CountMap.put(key, plays[i]);
        }
 
        // 주어진 조건대로 정렬
        List<Map.Entry<Integer, Integer>> playsList = new LinkedList<>(playsMap.entrySet());
 
        Collections.sort(playsList, new Comparator<Map.Entry<Integer, Integer>>() {
 
            @Override
            public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
 
                // 많이 재생된 장르를 먼저
                int iOrder = CountMap.get(genres[o2.getKey()]) - CountMap.get(genres[o1.getKey()]);
                // 많이 재생된 노래를 먼저
                iOrder = (iOrder == 0) ? o2.getValue() - o1.getValue() : iOrder;
                // 고유 번호가 낮은 노래를 먼저
                iOrder = (iOrder == 0) ? o1.getKey() - o2.getKey() : iOrder;
 
                return iOrder;
            }
        });
 
        // 장르별 최대 2곡씩 선택
        int count = 0;
        List<Integer> liAnswer = new ArrayList<Integer>();
        
        Iterator<Map.Entry<Integer, Integer>> iter = playsList.iterator();
        while (iter.hasNext()) {
            Map.Entry<Integer, Integer> entry = iter.next();
            
            if (count >= 2) {
                if (genres[liAnswer.get(liAnswer.size() - 1)].equals(genres[entry.getKey()])) {
                    continue;
                }
                count = 0;
            } 
            
            if (liAnswer.size() > 0 
                    && !genres[liAnswer.get(liAnswer.size() - 1)].equals(genres[entry.getKey()])) {
                count = 0;
            }
            
            if (count < 2) {
                liAnswer.add(entry.getKey());
                count++;
            }
        }
 
        // 리스트 -> 배열
        int[] answer = new int[liAnswer.size()];
        
        for (int i = 0; i < answer.length; i++) {
            answer[i] = liAnswer.get(i);
        }
        
        return answer;
    }
}