베스트앨범(프로그래머스, Lv 3, Java)

1. 베스트 앨범

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

알고리즘 설명:

장르를 해시로 관리하고 높은 값 2개만 가지고 있게 장르 객체를 관리해주면 끝

• Song이라는 클래스를 정의
  • 장르의 총 재생 수와 높은 재생 수의 인덱스 관리
  • 처음 객체가 생성될 때 두 번째 큰 인덱스 값으로 -1을 넣어주어 인덱스 0과 겹치지 않게 한다.
  • 장르의 새로운 노래가 들어올 때마다 setSong 메서드를 호출하여 높은 순으로 2개의 인덱스 업데이트
• ketSet을 사용하여 모든 장르를 불러오고 Song을 받는 list를 만들어 장르들의 객체를 넣어준다.
• 동시에 가지고 있는 노래의 개수를 체크하여 정답 배열의 사이즈를 체크
• 객체들의 sum 값 순으로 내림차순 정렬
• 차례대로 정답 배열에 넣어주고 리턴

코드(Java)

package coding;

import java.util.*;

public class BestAlbum {

	public static int[] solution(String[] genres, int[] plays) {
		Map<String, Song> map = new HashMap<>();

		for (int i = 0; i < genres.length; i++) {
			if (map.containsKey(genres[i])) {
				Song song = map.get(genres[i]);
				song.setSong(i, plays);
				map.put(genres[i], song);
			} else {
				Song song = new Song(plays[i], i);
				map.put(genres[i], song);
			}
		}
		Iterator<String> set = map.keySet().iterator();
		List<Song> list = new LinkedList<>();
		int size = 0;
		while (set.hasNext()) {
			String key = set.next();
			Song song = map.get(key);
			if (song.getNum()[1] == -1)
				size++;
			else
				size += 2;

			list.add(map.get(key));
		}
		Collections.sort(list, new Comparator<Song>() {
			@Override
			public int compare(Song o1, Song o2) {

				return o2.getSum() - o1.getSum();
			}
		});
		int[] answer = new int[size];
		int i = 0;
		for (Song song : list) {
			answer[i++] = song.getNum()[0];
			if (song.getNum()[1] != -1)
				answer[i++] = song.getNum()[1];
		}
		return answer;
	}

	public static class Song {
		int sum;
		int[] num;

		public Song(int play, int i) {
			num = new int[2];
			num[0] = i;
			num[1] = -1;
			sum = play;
		}

		public void setSong(int i, int[] plays) {
			sum += plays[i];
			if (plays[num[0]] < plays[i]) {
				num[1] = num[0];
				num[0] = i;
			} else if (num[1] == -1 || plays[num[1]] < plays[i]) {
				num[1] = i;
			}
		}

		public int[] getNum() {
			return num;
		}

		public int getSum() {
			return sum;
		}
	}

	public static void main(String[] args) {
		String[] g = { "classic", "pop", "classic", "classic", "pop" };
		int[] p = { 500, 600, 150, 800, 2500 };
		System.out.println(Arrays.toString(solution(g, p)));
	}

}