[Hash] 베스트 앨범 - Java 풀이★★★

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

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

 

문제

해당 문제를 잘 풀기 위해서는, 문제를 잘 이해하는게 제일중요하다.

일단, 

장르별로 Play횟수를 sum한 값을 저장해주어서, sort후 해당 장르에서 2곡씩 뽑아주어야 하는 문제이다.

장르별 Sum값은 Map을 이용하면 되지만,

곡의 가지는 정보는 id(인덱스), 장르, Play횟수  총 3가지 정보를 가지고 있으며,

각각의 속성별로 우선순위를 가지게 정렬해주어야 하므로, Song이라는 하나의 객체를 만들어주었다. 

 

풀이

package week10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/*
	속한 노래가 많이 재생된 장르를 먼저 수록합니다.
	장르 내에서 많이 재생된 노래를 먼저 수록합니다.
	장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
	
정확성  테스트
	테스트 1 〉	통과 (4.48ms, 73.8MB)
	테스트 2 〉	통과 (4.40ms, 78.1MB)
	테스트 3 〉	통과 (3.47ms, 77.1MB)
	테스트 4 〉	통과 (5.78ms, 79.5MB)
	테스트 5 〉	통과 (4.12ms, 76.1MB)
	테스트 6 〉	통과 (18.98ms, 85.7MB)
	테스트 7 〉	통과 (3.24ms, 70.2MB)
	테스트 8 〉	통과 (4.17ms, 82.1MB)
	테스트 9 〉	통과 (3.87ms, 67.9MB)
	테스트 10 〉	통과 (3.32ms, 76.9MB)
	테스트 11 〉	통과 (3.75ms, 74.4MB)
	테스트 12 〉	통과 (4.65ms, 76.4MB)
	테스트 13 〉	통과 (3.55ms, 75.6MB)
	테스트 14 〉	통과 (3.60ms, 76.8MB)
	테스트 15 〉	통과 (3.31ms, 76.7MB)

*/
public class 베스트앨범 {
	public static void main(String[] args) {
		String[] genres = {"classic", "pop", "classic", "classic", "pop"};
		int[] plays = {500, 600, 150, 800, 2500};
		int[] res = solution(genres, plays);
		for(int i : res)
			System.out.println(i);
	}

    public static int[] solution(String[] genres, int[] plays) {
    	Map<String , Integer> map = new HashMap<>();
    	ArrayList<Song> Songlist = new ArrayList<>();
    	
    	// 장르별 plays수 합계 저장, SongList에 곡 정보 저장
    	for(int i=0;i<plays.length;i++) {
    		map.put(genres[i], map.getOrDefault(genres[i],0) + plays[i]);
    		Songlist.add(new Song(genres[i] ,i ,plays[i]));
    	}
    	// 장르별 최댓값 정렬
    	ArrayList<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());
    	entryList.sort((Entry<String, Integer> o1, Entry<String, Integer> o2) -> o2.getValue() - o1.getValue());
    	// Song 정렬 (낮은번호 정렬후, 높은 Play수로 정렬)
    	Songlist.sort((o1,o2) -> o1.i - o2.i);
    	Songlist.sort((o1,o2) -> o2.p - o1.p);
    	// 해당 장르에 Best곡 2개 선정
    	ArrayList<Integer> list = new ArrayList<>();
    	for(Map.Entry<String, Integer> entry : entryList) {
    		int cnt=0;
    		for(Song s : Songlist) {
    			if(s.g.equals(entry.getKey())) {
    				list.add(s.i);
    				cnt++;
    			}
    			if(cnt==2) break;
    		}
    	}
    	return list.stream().mapToInt(i->i).toArray();
    }
}
class Song{
	String g;
	int i,p; // g는 장르, i는 곡 번호, p는 play횟수
	public Song(String g, int i, int p) {
		this.g = g;
		this.i = i;
		this.p = p;
	}
}

 

Map을 Value 정렬하기 위해서 Map.entry 와 익숙해질 필요가 있다.

list 객체를 array로 변환하기 위해 Stream을 사용하는데,

Stream은 아직 많이 사용하지 않았기에 잘 익숙해지도록 공부할 필요가 있어 보인다.

 

다른사람의 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
정확성  테스트
테스트 1 〉	통과 (6.63ms, 71.8MB)
테스트 2 〉	통과 (5.22ms, 80.9MB)
테스트 3 〉	통과 (7.39ms, 81.2MB)
테스트 4 〉	통과 (5.17ms, 79.7MB)
테스트 5 〉	통과 (6.24ms, 74.2MB)
테스트 6 〉	통과 (5.01ms, 74.3MB)
테스트 7 〉	통과 (7.00ms, 83.4MB)
테스트 8 〉	통과 (5.40ms, 77.6MB)
테스트 9 〉	통과 (4.91ms, 74.2MB)
테스트 10 〉	통과 (6.63ms, 79.8MB)
테스트 11 〉	통과 (4.62ms, 71.7MB)
테스트 12 〉	통과 (5.33ms, 77.7MB)
테스트 13 〉	통과 (7.52ms, 73.7MB)
테스트 14 〉	통과 (5.40ms, 70.6MB)
테스트 15 〉	통과 (4.84ms, 79.4MB)
 * @author CMN
 *
 */
public class _4_best_album3_just_practice {
	public static void main(String[] args) {
		String[] genres = {"classic", "pop", "classic", "classic", "pop"};
		int[] plays = {500, 600, 150, 800, 2500};
		int[] answer = solution(genres, plays);
		System.out.println(Arrays.toString(answer));
	}
	
	/**
	 * 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
	2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
	3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
	 * @param genres
	 * @param plays
	 * @return
	 */
	public static int[] solution(String[] genres, int[] plays) {
		int[] answer = {};
		Map<String, Integer> genreToPlayCntMap = new HashMap<>();
		Map<String, Map<Integer, Integer>> genreToSongIdPlayCntMap = new HashMap<>();
		//1. 데이터 초기화
		for (int i=0; i<genres.length; i++) {
			genreToPlayCntMap.put(genres[i], genreToPlayCntMap.getOrDefault(genres[i], 0) + plays[i]);
			Map<Integer, Integer> songIdToPlayCntMap = genreToSongIdPlayCntMap.getOrDefault(genres[i], new HashMap<>());
			songIdToPlayCntMap.put(i, songIdToPlayCntMap.getOrDefault(i, 0) + plays[i]);
			genreToSongIdPlayCntMap.put(genres[i], songIdToPlayCntMap);
		}
		//2. 요건에 맞게 정렬
		//2-1. 요건1. 가장 많이 재생된 장르
		String[] genreArray = genreToPlayCntMap.keySet().toArray(new String[0]);
		Arrays.sort(genreArray, (g1, g2) -> genreToPlayCntMap.get(g2) - genreToPlayCntMap.get(g1));
		System.out.println("genreArray: " + Arrays.toString(genreArray));
		//2-2. 요건2. 장르 내에서 가장 많이 재생된 노래 (최대 2개)
		//요건3. 동일 재생 시 고유 번호가 낮은 노래 순
		List<Integer> _answer = new ArrayList<>();
		for (int i=0; i<genreArray.length; i++) {
			Map<Integer, Integer> songIdAndPlayCntMap = genreToSongIdPlayCntMap.get(genreArray[i]);
			List<Integer> songIdList = new ArrayList<>(songIdAndPlayCntMap.keySet());
			songIdList.sort((i1, i2) -> 
				{
					int playCnt1 = songIdAndPlayCntMap.get(i1);
					int playCnt2 = songIdAndPlayCntMap.get(i2);
					if (playCnt1 != playCnt2) {
						return playCnt2 - playCnt1;
					} else {
						return i1 - i2;
					}
				});
			//3. 최대 2개씩 담기
			int j = 0;
			while (j < 2 && j < songIdList.size()) {
				System.out.println(j);
				_answer.add(songIdList.get(j));
				j++;
			}
		}
		answer = _answer.stream().mapToInt(Integer::intValue).toArray();
		return answer;
	}
}

 

Map안에 value속에 Map을사용해준것이 인상깊다.