[Programmers] 해시.베스트앨범 / HashMap

@HashMap / 30m

해시 연습하기 좋은 문제 + Comparable 연습하기도 좋다!

 

 

문제 링크

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

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

 

 

구현 방법

맵을 두개 써서 구현했다.

하나는 장르마다 총 재생 시간을 담은 맵

다른 하나는 장르마다 속한 곡들의 리스트를 담은 맵

 

 

1. <장르, 총 재생 횟수>를 담은 HashMap인 genreMap을 만든다.

 

2. Map의 내용을 List<Genre>인 genreList에 옮겨담은 후 (Genre 클래스 : 장르, 총 재생 횟수를 담은 클래스)

총 재생 횟수를 기준으로 내림차순 정렬한다.

 

3. <장르, List<Song>>를 담은 HashMap인 songListMap을 만든다. (Song 클래스 : 인덱스, 재생 횟수를 담은 클래스)

각 장르를 Key로 하고, 인덱스와 재생 횟수는 리스트로 만들어준다.

다 담고 나서는 songListMap의 value인 리스트들도 정렬해준다. (정렬 기준 : 재생 횟수, 횟수가 같으면 인덱스가 작은 순)

 

4. 2번에서 만든 List<Genre>을 돌면서, 해당 장르를 키로 갖고있는 songListMap의 value 리스트에서 2개씩(값이 1개만 있는경우는 1개만) 빼와서 answer에 담아준다.

 

그냥 생각나는 대로 풀어서.. 풀이를 쓰다보니 불필요하게 복잡하게 푼 것 같다는 생각이 든다.

다시 최적화 해보기!

 

 

코드

import java.util.*;

public class 베스트앨범 {

	class Genre implements Comparable<Genre> {
		String genre;
		int playCountSum;

		Genre(String genre, int playCountSum) {
			this.genre = genre;
			this.playCountSum = playCountSum;
		}

		@Override
		public int compareTo(Genre o) {
			return -1 * (this.playCountSum - o.playCountSum);
		}
	}

	class Song implements Comparable<Song> {
		int idx, playCount;

		Song(int idx, int playCount) {
			this.idx = idx;
			this.playCount = playCount;
		}

		@Override
		public int compareTo(Song o) {
			if (this.playCount != o.playCount) {
				return -1 * (this.playCount - o.playCount);
			} else {
				return this.idx - o.idx;
			}
		}
	}

	public int[] solution(String[] genres, int[] plays) {
		Map<String, Integer> genreMap = new HashMap<String, Integer>();
		Map<String, LinkedList<Song>> songListMap = new HashMap<String, LinkedList<Song>>();
		
		//재생횟수 총합을 genreMap에 넣어주고, 각 장르에 대한 재생횟수와 인덱스를 map에 넣어준다 
		for (int i = 0; i < genres.length; i++) {
			if (genreMap.containsKey(genres[i])) {
				genreMap.put(genres[i], genreMap.get(genres[i]) + plays[i]);
			} else {
				genreMap.put(genres[i], plays[i]);
				songListMap.put(genres[i], new LinkedList<Song>());
			}
			songListMap.get(genres[i]).add(new Song(i, plays[i]));
		}

		//재생횟수와 장르 이름을 genreList에 넣어준다. 
		ArrayList<Genre> genreList = new ArrayList<Genre>();
		for (String key : genreMap.keySet()) {
			genreList.add(new Genre(key, genreMap.get(key)));
			Collections.sort(songListMap.get(key));
		}
		//재생횟수가 많은 순으로 정렬해준다. 
		Collections.sort(genreList);

		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < genreList.size(); i++) {
			for (int j = 0; j < songListMap.get(genreList.get(i).genre).size(); j++) {
				if (j == 2)
					break;
				list.add(songListMap.get(genreList.get(i).genre).get(j).idx);
			}
		}
		
		int[] answer = new int[list.size()];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = list.get(i);
		}
		return answer;
	}
}

재미있는 문제였다. 끝!