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

문제보러가기

코딩테스트 연습 - 베스트앨범

이문제는 해시와 정렬을 이용해 풀 수 있는 문제였다. 깔끔하게 풀고 싶었으나 답이 나오게 문제를 풀기만 한 것 같다...ㅎ

 

 

 

 

 

문제풀이

-장르별로 어떤 노래가 있는지 구분하기 위해 Map을 이용해 저장해준다.

-각 장르 안에서 노래들은 재생 횟수가 높은 순, 같은 재생 횟수일 경우 고유번호(인덱스가 사용됨)가 낮은 순으로 저장할 수 있도록 PriorityQueue를 사용하고 정렬 기준을 정해주기 위해  compareTo함수를 구현해 준다.

-장르별  재생 횟수를 구해서 가장 높은 재생 횟수를 기록하는 장르가 먼저 앨범에 수록될 수 있도록 장르(key), 장르별 재생 횟수(value)로 저장한 후 정렬해 준다.

 

-**여기서 내가 헷갈렸던 부분은 각 장르별 2개 노래를 뽑는데, 장르별 재생 횟수를 구할 때는 2개가 아닌 장르에 해당하는 전체 노래의 재생 횟수를 더해야 한다는 부분!

 

-그 후에 재생 횟수로 정렬한 맵에서 해당 장르의 노래를 2개씩 뽑아와 정답 배열에 순서대로 저장한다.

 

-**여기서도 고려해야 될 부분! 해당 장르의 노래가 2개가 아니고 1개일 수 있다. 이 부분을 고려하여 처리해줘야 한다.

 

 

 

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class Solution {

	public static void main(String[] args) {

		String[] genres= {"classic", "pop", "classic", "classic", "pop","zazz","zazz"};
		int[] plays = {500, 600, 150, 800, 2500,4000,100};
		int ansSize=0;
		HashMap<String,PriorityQueue<Song>> map = new HashMap<>();
        //장르,장르에 해당하는 노래로 map에 저장
		for(int i=0;i<plays.length;i++) {
			PriorityQueue<Song> list;
			if(map.containsKey(genres[i])) {
				list = map.get(genres[i]);
				if(map.get(genres[i]).size()==1) ansSize++;
			}else {
				list = new PriorityQueue<>();
				ansSize++;
			}
			list.add(new Song(i,plays[i]));
			map.put(genres[i], list);
		}
		int[] answer = new int[ansSize];
        //장르별 총 재생횟수를 세어 장르와 함께 저장하고 내림차순 될 수 있도록 정렬구현
		Comparator<Integer> comparator = (o1, o2)->o2.compareTo(o1);
		Map<Integer, String> sortingMap = new TreeMap<>(comparator);
		for(String key : map.keySet()) {
			int sum = 0;
			int size = map.get(key).size();
			PriorityQueue<Song> val = new PriorityQueue<Song>();
			for(int i=0;i<size;i++) {
				Song song = map.get(key).poll();
				sum += song.play;
				val.add(song);
			}
			map.put(key, val);
			sortingMap.put(sum, key);
		}
        //위에서 재생횟수로 정렬된 key값인 장르를 꺼내어 
        //처음에 정보가 저장된 map에서 노래를 뽑아 answer배열에 저장한다
		int index=0;
		for(Integer i : sortingMap.keySet()) {
			String key = sortingMap.get(i);
			if(map.get(key).size()==1) {
				answer[index++] = map.get(key).poll().no;				
			}else {
				answer[index++] = map.get(key).poll().no;
				answer[index++] = map.get(key).poll().no;
			}
		}
		for(int i : answer) {
			System.out.println(i);
		}
		
		
		
	}

}
class Song implements Comparable<Song>{
	int no;
	int play;
	Song(int no, int play){
		this.no = no;
		this.play = play;
	}
	public int compareTo(Song s) {
        if(this.play > s.play) {
            return -1; // 내림차순
        }
        else if(this.play== s.play) {
            if(this.no < s.no) {
                return -1;
            }
        }
        return 1; 
    }
	
}