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

프로그래머스 고득점 알고리즘 kit의 마지막 문제인 베스트 앨범이다.

 

 

✅ 핵심 풀이

 

문제에 나온 1번째 조건인 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 을 만족하기 위해

장르 별 노래 재생 횟수를 count 하고 저장하기 위해 Map<String(장르명), Integer(재생횟수)> 을 사용하고

Map 내 value (재생 횟수) 를 기준으로 key(장르) 를 내림차순 정렬한다.

장르의 정렬 결과를 List<String>에 저장하고 정렬된 장르(rankedGenre)를 기준으로 genres 배열을 순회하여 

rankedGenre == genres[i] 인 경우 해당 노래의 genre와 재생 횟수인 play,

그리고 해당 노래가 배열의 몇 번째 원소였는지에 대한 idx를 Album 객체의 리스트인 list에 저장해주었다.

이후 문제의 2번째 조건 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 를 만족하기 위해

list를 내림차순 정렬해준다.

문제의 3번째 조건인 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

같은 경우, Album 객체를 저장하는 list에 idx가 낮은 순 부터 add하기 때문에 자동으로 만족하게 된다.

(재생 횟수가 같은 경우, o1 과 o2의 순번이 바뀌지 않게 된다.)

 

🚨 CODE

import java.io.*;
import java.util.*;

public class Main {

	static class Album{
		String genre;
		int play;
		int idx;
		
		public Album(String genre, int play, int idx) {
			this.genre = genre;
			this.play = play;
			this.idx = idx;
		}
	}
	
	public static void main(String[] args) throws IOException{
		
		String[] genres = {"classic", "pop", "classic", "classic", "pop"};
		int[] plays = {500, 600, 150, 800, 2500};
		
		
		int[] result = solution(genres, plays);
		for(int res : result) {
			System.out.print(res + " ");
		}
	}
	
	public static int[] solution(String[] genres, int[] plays) {
		
		// 장르 중 재생 횟수가 가장 많은 순 대로 sort
		Map<String, Integer> genrePlayCount = new HashMap<>();
		for(int i = 0; i<genres.length; i++) {
			genrePlayCount.put(genres[i], genrePlayCount.getOrDefault(genres[i], 0) + plays[i]);
		}
		
		List<String> genreRanks =  getGenreRank(genrePlayCount);
		
		List<Album> result = new ArrayList<>();
		// genres 를 탐색해 해당되는 장르가 있다면 list에 add
		for(String rankedGenr : genreRanks) {
			List<Album> list = new ArrayList<>();
			for(int i = 0; i<genres.length; i++) {
				if(rankedGenr.equals(genres[i])) {
					list.add(new Album(rankedGenr, plays[i], i));
				}
			}
			
			// 해당 장르 내 재생 횟수가 많은 순 대로 sort
			Collections.sort(list, (o1, o2) -> o2.play - o1.play);
			// 적어도 노래 1곡은 넣어야 하므로 get(0) add
			result.add(list.get(0));
			// 노래가 1곡만 있는게 아니라면
			if(list.size()!= 1) {
				result.add(list.get(1));
			}
		}
		int[] answer = new int[result.size()];
		for(int i = 0; i<result.size(); i++) {
			answer[i] = result.get(i).idx;
		}
		
		return answer;
	}
	
	public static List<String> getGenreRank(Map<String, Integer> rank) {
		List<String> genreRank = new ArrayList<>(rank.keySet());
		genreRank.sort((o1, o2) -> rank.get(o2).compareTo(rank.get(o1)));
		return genreRank;
	}	
}