프로그래머스 - 베스트 앨범

프로그래머스 - 베스트 앨범

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
	public int[] solution(String[] genres, int[] plays) {
		// 장르 : 플레이 수 맵 생성
		// 장르 : 총 재생 수 맵 생성
		// 1. 장르 : 총 재생 수 맵을 keySet 정렬하여 가장 처음꺼
		// 1-1. 장르를 가져오고, 해당 배열 인덱스 값 정렬하여 2개 선출(1개라면 1개만)
		// 1-2. 재생 횟수가 같으면 고유 번호가 낮은 노래 먼저(인덱스)
		Map<String, ArrayList<Integer>> genreMap = new HashMap<>();
		Map<String, Integer> playMap = new HashMap<>();

		// 장르별 인덱스 저장, 총합 저장 맵 생성
		for (int i = 0; i < genres.length; i++) {
			String g = genres[i];
			genreMap.putIfAbsent(g, new ArrayList<>());
			genreMap.get(g).add(plays[i]);

			Integer playSum = playMap.getOrDefault(g, 0) + plays[i];
			playMap.put(g, playSum);
		}

		List<Map.Entry<String, Integer>> sortedList = playMap.entrySet()
			.stream()
			.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
			.collect(Collectors.toList());

		List<Integer> resultList = new ArrayList<>();

		for (Map.Entry<String, Integer> entry : sortedList) {
			ArrayList<Integer> playCount = genreMap.get(entry.getKey());
			// 장르 내에서 많은 재생 횟수
			playCount.sort(Comparator.reverseOrder());
			// 장르 내에서 재생 횟수가 같다면 인덱스 적은 순으로 저장 리스트
			ArrayList<Integer> indexs = new ArrayList<>();

			for (int a : playCount) {
				// 2개가 아직 안됐으면 찾기
				for (int i = 0; i < plays.length; i++) {
					if (a == plays[i]) {
						// 없으면 추가하고 종료, 있으면 다음꺼 찾게
						if(!indexs.contains(i)) {
							indexs.add(i);
							// 같은게 2개 이상이라면 빠른 인덱스부터 추가되게
							break;
						}
					}
				}

				// 장르에 속한 곡이 1개라면 해당 인덱스 찾아서 넣고 바로 종료
				// 위에서 어차피 인덱스 찾았으므로 그냥 바로 종료 시켜도 됨
				if (playCount.size() == 1) {
					break;
				}

				// 2개 이상이 속해있다면, 인덱스가 2개를 찾으면 종료
				else if (indexs.size() == 2) {
					break;
				}
			}
			// 해당 장르를 결과에 넣기 -> 총 재생횟수 순으로 진행되니 순서대로 들어감
			resultList.addAll(indexs);
		}

		return resultList.stream().mapToInt(Integer::intValue).toArray();
	}
}

구현 방법 1

• EntrySet을 스트림을 활용하여 내림차순 정렬
• 그러면 이제 가장 많은 play수 총합을 가진 장르 순으로 정렬 되니, 내림차순 정렬된 키 값을 하나씩 가져오며 해당하는 play수 가진 리스트를 가져옴
• 그 리스트의 play수를 해당하는 인덱스를 찾고 인덱스를 추가해준다.
  • 플레이 수가 같다면 빠른 번호 순으로 하기 위해 먼저 발견하면 브레이크
  • 하지만 이렇게하면 같은 번호가 두번 들어갈 수 있으므로 기존에 들어가 있는지 검사
• 장르에 소속된 음악이 1개면 인덱스 1개만 추가하면 되므로 종료
• 인덱스에 2개가 차면 종료하고 결과 리스트에 추가

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
	public int[] solution(String[] genres, int[] plays) {
		// 1. Map 생성
		HashMap<String, Integer> playCountMap = new HashMap<>();
		HashMap<String, List<Integer>> genrePlayIndexMap = new HashMap<>();
		for (int i = 0; i < genres.length; i++) {
			String genre = genres[i];
			// 장르별 음악 재생 횟수 합 저장
			playCountMap.put(genre, playCountMap.getOrDefault(genre, 0) + plays[i]);
			// 장르별 음악 인덱스 저장하기
			List<Integer> genrePlayCountList = genrePlayIndexMap.getOrDefault(genre, new ArrayList<>());
			genrePlayCountList.add(i);
			genrePlayIndexMap.put(genre, genrePlayCountList);
		}

		// 2. 재생 많이된 장르 먼저 수록
		List<Map.Entry<String, Integer>> entrySetSortedList = playCountMap.entrySet()
			.stream()
			.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
			.collect(Collectors.toList());

		// 3. 정답 찾기
		List<Integer> result = new ArrayList<>();
		for (Map.Entry<String, Integer> entry : entrySetSortedList) {
			List<Integer> list = genrePlayIndexMap.get(entry.getKey());
			// 해당 장르 음악이 1개라면 그냥 해당 인덱스 추가
			if (list.size() == 1) {
				result.add(list.get(0));
				continue;
			}
			// 음악 2개 이상이라면 재생 횟수가 많은 순으로 정렬 후 삽입, 같을 경우 인덱스 낮은 순
			List<Integer> sortedList = list.stream()
				.sorted((o1, o2) -> {
						int play1 = plays[o1];
						int play2 = plays[o2];
						if (play1 == play2) {
							// 재생 횟수가 같은 경우, 인덱스가 낮은 노래가 먼저 오도록 변경
							return o1 - o2;
						} else if (play1 < play2) {
							// 양수 반환 : 첫 번째 인자가 두번째 인자보다 큼(왼 > 오)
							// 항상 큰것이 뒤로 가게 정렬되기 때문에 왼쪽꺼가 뒤로 가짐
							// Comparator : 양수일 경우 첫번째가 뒤에 나옴
							return 1;
						}
						// play1 > play2
						else {
							// 음수 반환 : 첫 번째 인자가 두번째 인자보다 작음(왼 < 오)
							// 첫번째 인자가 항상 작으니 첫번째꺼가 앞에옴
							// Comparator : 음수일 경우 첫번째가 앞에 나옴
							return -1;
						}
					}
				)
				.collect(Collectors.toList());

			for (int idx = 0; idx < sortedList.size(); idx++) {
				// 2개 까지만 넣기
				if (idx >= 2) {
					break;
				}
				result.add(sortedList.get(idx));
			}
		}

		// 4. 반환
		return result.stream()
			.mapToInt(Integer::intValue)
			.toArray();

	}
}

구현 방법 2

• 2가지 Map 생성
  • playCountMap : 장르별 재생 수 총합
  • genrePlayIndexMap : 장르별 음악 인덱스
• Map.Entry 이용하여 playCountMap의 value 값을 기준으로 내림차순 정렬
• 순회하며 만약 해당 장르에 해당하는 음악 리스트가 1개면 결과에 추가하고 다음 반복
• 리스트가 2개 이상이라면 문제에 나온 정렬 조건 적용 후 2개 까지만 추가
  • Comparator 객체 구현
  • 반환 결과 양수 : 첫 번째 인자(o1)가 뒤에 나옴
  • 반환 결과 음수 : 첫 번째 인자(o2)가 앞에 나옴
• 결과 배열로 반환