[JAVA] Programmers <Hash_LV3> 베스트 앨범

처음엔 무작정 로직을 그대로 구현하려고 마음을 먹었다. 복잡해 보이는 문제일수록 오히려 한번 데이는 것이 좀 더 효율적인 방법을 빠르게 찾는 방법인 경우도 때때로 있었으니...그러나 제한 사항을 두번, 세번 보다가 문득, 이 문제는 Comparable이나 Comparator을 사용하지 않으면 진짜 엄청난 노가다 문제가 될 것 같다는 확신이 들었다.

객체와 sort를 이용한 해결 방법은 다음과 같다.

 

1. plays, ids를 인자로 갖는 SongInfo 객체를 조회수 내림차순, id 오름차순으로 정렬할 Comparable 과 함께 생성

2. 조회수의 누적합 totalPlays와 SongInfo의 ArrayList를 인자로 갖는 GenresInfo 객체를 totalPlays 내림차순으로 정렬할 Comparable 과 함께 생성

3. <장르 이름, GenresInfo>의 Map 생성

4. Map의 장르 이름별로 값을 삽입하며 totalPlays 를 증가시킴

5. 삽입이 끝나면 Map의 크기를 갖는 genresInfoList 생성

6. Map을 이터레이션 돌리면서 genresInfoList에 value를 삽입 후 각 GenresInfo 객체가 가지고 있는 SongList를 sort시킴

7. resultList 생성 후 genresInfoList를 이터레이션 돌리며 각 SongInfoList의 크기를 확인 후 answer에 삽입

 

끝!

 

코드는 다음과 같으며 이 문제를 푸는 동안 hashMap 보다는 Comparable, Comparator의 사용법을 완전히 깨우쳤다.

(나름 괜찮은건가...ㅎ)

 

Code: 

package com.choonham;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;

public class Solution {

	public Solution() {
		// TODO Auto-generated constructor stub
	}

	public int[] solution(String[] genres, int[] plays) {
		HashMap<String, GenresInfo> hm = new HashMap<>();
		for (int i = 0; i < genres.length; i++) {
			if(!hm.containsKey(genres[i])) {
				hm.put(genres[i], new GenresInfo(plays[i], new ArrayList<SongInfo>()));
				hm.get(genres[i]).SongInfoList.add(new SongInfo(plays[i], i));
			} else {
				 hm.get(genres[i]).setTotalPlays(hm.get(genres[i]).getTotalPlays() + plays[i]);
				 hm.get(genres[i]).SongInfoList.add(new SongInfo(plays[i], i));
			}
		}
		
		GenresInfo[] genresList = new GenresInfo[hm.size()];
		
		int i = 0;
		
		for(Entry<String, GenresInfo> e : hm.entrySet()) {
			genresList[i++] = e.getValue();
			Collections.sort(e.getValue().getSongInfoList());
		}
		
		Arrays.sort(genresList);
		
		ArrayList<Integer> resultList = new ArrayList<>();
		for(GenresInfo g : genresList) {
			ArrayList<SongInfo> songList = g.getSongInfoList();
			int each = songList.size();
			
			if(each == 1) {
				resultList.add(songList.get(0).getIds());
			}
			else {
				for(int j = 0; j < 2; j++) {
					resultList.add(songList.get(j).getIds());
				}
			}
		}	
		
		int resultSize = resultList.size();
		int[] answer = new int[resultSize];
		
		for (int j = 0; j < resultSize; j++) {
			answer[j] = resultList.get(j);
		}

		return answer;
	}

	class GenresInfo implements Comparable<GenresInfo> {
		private int totalPlays;
		private ArrayList<SongInfo> SongInfoList;
		
		public GenresInfo(int totalPlays, ArrayList<SongInfo> SongInfoList) {
			this.totalPlays = totalPlays;
			this.SongInfoList = SongInfoList;
		}

		public int getTotalPlays() {
			return totalPlays;
		}

		public void setTotalPlays(int totalPlays) {
			this.totalPlays = totalPlays;
		}

		public ArrayList<SongInfo> getSongInfoList() {
			return SongInfoList;
		}

		public void setSongInfoList(ArrayList<SongInfo> songInfoList) {
			SongInfoList = songInfoList;
		}

		@Override
		public int compareTo(GenresInfo o) {
			if (totalPlays > o.totalPlays)
				return -1;
			else if (totalPlays == o.totalPlays)
				return 0;
			return 1;
		}
	}

	class SongInfo implements Comparable<SongInfo>{
		private int plays;
		private int ids;
		@Override
		public int compareTo(SongInfo o) {
			if(plays > o.plays || (plays == o.plays) && (ids < o.ids)) return -1;
			else return 1;
		}
		public SongInfo(int plays, int ids) {
			this.plays = plays;
			this.ids = ids;
		}
		public int getPlays() {
			return plays;
		}

		public void setPlays(int plays) {
			this.plays = plays;
		}

		public int getIds() {
			return ids;
		}

		public void setIds(int ids) {
			this.ids = ids;
		}

	}
}