프로그래머스 베스트앨범 자바 풀이(해시04)

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genresplaysreturn

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

#풀이

---

	class Solution {
		public List<Integer> solution(String[] genres, int[] plays) {
			ArrayList<Integer> answer = new ArrayList<Integer>();

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

			// map: 장르1:{음악1, 음악2}, 장르2:{음악3}, 장르3:{음악4, 음악5}
			for (int i = 0; i < genres.length; i++) {
				if (!map.containsKey(genres[i])) {
					list = new ArrayList<>();
					map.put(genres[i], list);
				}
				map.get(genres[i]).add(new Music(i, genres[i], plays[i]));
			}
			
			//#Comparator1
			// 장르 간 play합 순으로 순서정렬위한 comparator (뒤의 treemap 선언 시 넣을것)
			Comparator<String> comparator = new Comparator<String>() {
				@Override
				/*pop(o1) classic(o2)
				 * 위의 map<String, ArrayList<Music>>에 의해
				 * map.get(o1)은 pop의 ArrayList를 얻을 수 있음.
				 * for문을 통해 map.get(o1).get(i)을 할 시 이 리스트안의
				 * pop음악들(pop1, pop2, pop3...)을 얻을 수 있고 이 합으로 비교				
				 */
				public int compare(String o1, String o2) {
					int sum1 = 0;
					int sum2 = 0;
					for (int i = 0; i < map.get(o1).size(); i++) {
						sum1 += map.get(o1).get(i).play;
					}
					for (int i = 0; i < map.get(o2).size(); i++) {
						sum2 += map.get(o2).get(i).play;
					}
					return sum2 - sum1;
				}
			};

			TreeMap<String, ArrayList<Music>> newmap = new TreeMap<>(comparator);
			newmap.putAll(map);
			
			//#Comparator2
			// 장르 간 play합 순으로 순서정렬 logic
			// 같은장르 내 순서정렬 1순위.count 2순위.idx
			for (Map.Entry<String, ArrayList<Music>> m : newmap.entrySet()) {
				Collections.sort(m.getValue(), new Comparator<Music>() {
					@Override
					public int compare(Music o1, Music o2) {
						if (o1.play == o2.play) {
							return o1.idx - o2.idx;
						} else {
							return o2.play - o1.play;
						}
					}
				});
			}

			for (Map.Entry<String, ArrayList<Music>> m : newmap.entrySet()) {
				if (m.getValue().size() == 1) {
					answer.add(m.getValue().get(0).idx);
				} else {
					answer.add(m.getValue().get(0).idx);
					answer.add(m.getValue().get(1).idx);
				}
			}

			return answer;
		}

		class Music {
			int idx;
			String genre;
			int play;

			Music(int idx, String genre, int play) {
				this.idx = idx;
				this.genre = genre;
				this.play = play;
			}
		}

	}

---

총 리스트 2개,맵 2개, 커스텀클래스 1개를 사용했다.

 

• 커스텀클래스 Music을 만들고 음악인덱스(idx), 음악장르(genre), 음악재생횟수(count) 세가지 데이터를 가지게 만들었다.

		class Music {
			int idx;
			String genre;
			int play;

			Music(int idx, String genre, int play) {
				this.idx = idx;
				this.genre = genre;
				this.play = play;
			}
		}

---

• 맵1(HashMap): (key:value)가 (장르:해당장르의 Music객체 리스트) 인 해쉬맵을 만들었다.
• 리스트1(ArrayList) : Music객체를 넣어준다. for문을 돌리면서 new로 새로운 리스트를 생성하여 맵의 value로 넣어준다.

			HashMap<String, ArrayList<Music>> map = new HashMap<>();
			// map: 장르1:{음악1, 음악2}, 장르2:{음악3}, 장르3:{음악4, 음악5}
			for (int i = 0; i < genres.length; i++) {
				if (!map.containsKey(genres[i])) {
					list = new ArrayList<>();
					map.put(genres[i], list);
				}
				map.get(genres[i]).add(new Music(i, genres[i], plays[i]));
			}

그리고 Comparator을 정의해서 sorting했는데, 해당장르의 모든음악의 재생횟수의 합 을 기준으로 장르들끼리의 순서를 비교하도록 했다.

			//#Comparator1
			// 장르 간 play합 순으로 순서정렬위한 comparator (뒤의 treemap 선언 시 넣을것)
			Comparator<String> comparator = new Comparator<String>() {
				@Override
				/*pop(o1) classic(o2)
				 * 위의 map<String, ArrayList<Music>>에 의해
				 * map.get(o1)은 pop의 ArrayList를 얻을 수 있음.
				 * for문을 통해 map.get(o1).get(i)을 할 시 이 리스트안의
				 * pop음악들(pop1, pop2, pop3...)을 얻을 수 있고 이 합으로 비교				
				 */
				public int compare(String o1, String o2) {
					int sum1 = 0;
					int sum2 = 0;
					for (int i = 0; i < map.get(o1).size(); i++) {
						sum1 += map.get(o1).get(i).play;
					}
					for (int i = 0; i < map.get(o2).size(); i++) {
						sum2 += map.get(o2).get(i).play;
					}
					return sum2 - sum1;
				}
			};
            
			TreeMap<String, ArrayList<Music>> newmap = new TreeMap<>(comparator);
			newmap.putAll(map);

그리고 이 Comparator을 새로운 Treemap을 만든 후 선언시 인자로 넣어주었다. 정리하자면 순서는,

1. (장르:해당장르의 모든 Music 객체들의 리스트) 의 구성을 가지는 HashMap(map) 선언, 데이터삽입 

2. TreeMap(newmap)선언 후, putAll메서드를 이용해서 기존의 HashMap(map)의 모든 요소를 넣어준다.

3. 이때 TreeMap 선언 전, 임의의 Comparator을 정의한 후 인자에 넣어준다.

굳이 TreeMap을 선언 한 후 넣어준 이유는, HashMap이 Key별로 순서를 정렬할 수 있는 방법이 없기때문이다. TreeMap은 기본적으로 데이터를 넣을때, 각 요소들의 key값을 비교하여 넣어준다(Comparator). 우선순위큐와 비슷하다고 볼 수도 있다. 이때 선언 시 어떠한 인자도 넣지 않으면 기본값인 Comparator가 작동하여 key값이 숫자이면 오름차순, 문자이면 사전순으로 배열을 해준다. 이 문제에서는 Key값을 장르로 두었고 각장르의 모든 음악의 재생횟수의 합으로 장르별로 정렬을 해야하기 때문에 임의의 Comparator을 정의하였다.

---

---

• 맵2(TreeMap) : 위의 HashMap과 요소는 같으나 Comparator로 순서가 정렬된 상태인 TreeMap이다. 장르사이에 순서가 정렬되었으니 이제는 장르안에서 각 음악객체끼리 비교를 하도록한다.

			//#Comparator2
			// 장르 간 play합 순으로 순서정렬 logic
			// 같은장르 내 순서정렬 1순위.count 2순위.idx
			for (Map.Entry<String, ArrayList<Music>> m : newmap.entrySet()) {
				Collections.sort(m.getValue(), new Comparator<Music>() {
					@Override
					public int compare(Music o1, Music o2) {
						if (o1.play == o2.play) {
							return o1.idx - o2.idx;
						} else {
							return o2.play - o1.play;
						}
					}
				});
			}

Comparator1은 Comparator자체를 정의하기만 했지만(TreeMap의 인자로 넣을 것이기 때문) TreeMap에서 key간 순서정렬이 끝난 상태이고 이제 value내에서 비교를 하는 것이기때문에 Collections.sort메서드를 사용한다. 각 음악별 재생횟수로 정렬한다

---

• 리스트2(ArrayList) : 정답을 담아줄 것이다.

			for (Map.Entry<String, ArrayList<Music>> m : newmap.entrySet()) {
				if (m.getValue().size() == 1) {
					answer.add(m.getValue().get(0).idx);
				} else {
					answer.add(m.getValue().get(0).idx);
					answer.add(m.getValue().get(1).idx);
				}
			}

			return answer;

문제의 조건에 따라 만약, 해당장르의 음악이 한개밖에 없다면 맨 앞의 하나만 answer에 삽입한다. 2개이상인 경우에는 위의 두번의 Comparator처리 과정에 의해 재생횟수별로 내림차순 되어있으므로 0번, 1번 인덱스를 answer에 담으면된다.

 

Map

putAll : Map1에 있는 요소들을 Map2에 그대로 담는데 사용된다. 배열의 clone()와 비슷한 역할