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

코딩테스트 풀이.. 알고리즘이나 코딩테스트를 공부하지만 아직 너무어렵다..

혼자풀기엔 힘들어서 구글링으로 블로그글중 이해하기 쉽게 쓴 글이 있어서 가져왔다. 

https://codevang.tistory.com/293

 

문제

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

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]번 노래를 그다음에 수록합니다.

 

풀이

 

문제의 핵심 과정에서 구해야할 것은 아래와 같습니다.

 

1. 장르별 총 조회수 합계 - 장르 정렬을 위함

2. 장르에 속한 개별 노래 정보(조회수, 인덱스) - 정렬 후 상위 순서 1~2개 뽑아냄

 

두 개가 다입니다. 저는 두 가지를 한번에 해결하기 위해 객체를 사용했습니다. 하나의 장르는 하나의 객체를 가지고, 이 객체 안에 총 조회수 합계 정보와 속한 노래 정보 리스트를 가지고 있는 구조입니다. 정렬을 할 때 컬렉션 계열에서 사용할 객체는 Comparator 인터페이스를 구현한 객체를 따로 만들어줘야 하고, 일반 배열을 사용할 객체는 Comparable 인터페이스를 구현해줘야 합니다. 고정된 배열을 사용할 것인지 유동적으로 변하는 리스트가 필요한지 결정해서 적절히 구현해주면 됩니다.

 

중복 문자열을 걸러줘야 하는만큼 HashMap을 사용합니다. 해시맵의 key는 장르 이름으로, value는 위의 장르 저장 객체로 설정합니다. 이렇게 하면 해시맵에 딱 하나의 장르가 생기게 되고 이 장르 안에 모든 정보가 포함되기 때문에 좀 더 편리하게 구조를 잡을 수 있을 것 같습니다.

그리고 배열의 정보를 이용해 해시맵을 완성시켜줍니다. 순회 한번에 모든 작업을 끝낼 수 있도록 했습니다. 어차피 장르의 모든 조회수 합계를 구하려면 배열을 모두 순회해야하고, 개별 노래정보를 알기 위해서도 마찬가지입니다. 해시맵에 담을 객체인 장르 저장 객체(GenresInfo)에 모든 곡정보까지 다 담기기 때문에 자료구조만 잘 잡으면 한번에 해결할 수 있게 됩니다. 

 

이제 "하나의 장르객체 - 총 조회수, 개별노래정보 리스트"가 완성되었으므로 정렬만 잘 해주면 됩니다. 해시맵은 정렬이라는 개념이 없으므로 일단 일반 배열로 꺼내줍니다. 이 때 해시맵은 모두 순회해야하므로 장르객체 안에 있는 개별노래정보 리스트의 정렬도 한번에 수행해줬습니다.

 

개별 노래 정보는 몇 개가 생길지 알 수 없어 컬렉션 List를 사용했기 때문에 정렬을 하기 위한 Comparator 객체를 하나 만든 뒤 정렬해줍니다. 장르 정보는 map에서 갯수가 확정됐기 때문에 일반 배열을 사용했습니다. 

 

여기까지 과정으로 장르 객체 안에 있는 개별 노래 정보들이 모두 정렬됐고, 장르객체도 일반 배열로 바꿔줬습니다. 이제 마지막 작업으로 장르객체를 총조회순으로 정렬한 뒤 각자가 가진 개별 정보 노래 리스트의 상위 1~2개만 순서대로 꺼내서 리스트에 추가해주면 됩니다.

 

그리고 문제에서 int[] 타입을 리턴하도록 했으므로 최종적으로 일반 배열로 변환한 뒤 리턴해주면 됩니다. 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
      Map<String, GenresInfo> map = new HashMap<>();
		
		for(int i=0; i<genres.length; i++) {
			//아직 추가되지 않은 장르는 새로만들어서 추가해야함.
			if(!map.containsKey(genres[i])) {
				//새로운 GenresInfo 객체를 생성 
				map.put(genres[i], new GenresInfo(plays[i], new ArrayList<SongInfo>()));
				//현재 순서의 노래정보 추가
				map.get(genres[i]).getSongInfo().add(new SongInfo(plays[i], i));
				//이미 존재하는 장르의 경우 
			}else {
				//총 조회수를 증가시킴 
				GenresInfo temp = map.get(genres[i]);
				temp.setPlays(temp.getPlays() + plays[i]);
				//노래 정보 추가 
				temp.getSongInfo().add(new SongInfo(plays[i], i));
			}
		}
		class SongInfoListSort implements Comparator<SongInfo> {

			@Override
			public int compare(SongInfo s1, SongInfo s2) {
				// 조회수 기준 내림차순 정렬, 같은 경우 인덱스기준 오름차순 정렬 
				if(s1.getCntPlays() < s2.getCntPlays() 
						|| (s1.getCntPlays() == s2.getCntPlays() 
						&& (s1.getIndex() > s2.getIndex()))) {
					return 1;
				}
				return -1;
			}
			
		}
		
		//장르정보를 배열로 바꾸면서 동시에 각 장르가 가진 노래리스트를 조회수로 정렬
		GenresInfo[] genresInfoList = new GenresInfo[map.size()];
		int k =0;
		for(Entry<String, GenresInfo> e : map.entrySet()) {
			genresInfoList[k++] = e.getValue();
			//각 장르안의 노래 리스트 정렬
			e.getValue().getSongInfo().sort(new SongInfoListSort());
		}
		//장르배열 정렬 및 각 장르안의 리스트의 노래정보에서 최대 2개까지만 인덱스 정보를 가져옴 
		Arrays.sort(genresInfoList);
		List<Integer> result = new ArrayList<>();
		for(GenresInfo g : genresInfoList) {
			List<SongInfo> list = g.getSongInfo();
			int size = list.size();
			//1개인 경우 
			if(size == 1) {
				result.add(list.get(0).getIndex());
			}else {
				//2개인 경우 
				for(int i=0; i<2; i++) {
					result.add(list.get(i).getIndex());
				}
			}
		}
		int resultSize = result.size();
		int[] answer = new int[resultSize];
		for(int i=0; i<resultSize; i++) {
			answer[i] = result.get(i);
		}
		return answer;
    }
}
class GenresInfo implements Comparable<GenresInfo> {

	private int plays;	//총 조회수 
	private List<SongInfo> songInfo;	//장르에 속한 노래정보 리스트 
	
	public GenresInfo(int plays, List<SongInfo> songInfo) {
		this.plays = plays;
		this.songInfo = songInfo;
	}
	//정렬기준 
	@Override
	public int compareTo(GenresInfo g) {
		// 총 조회수 내림차순 
		if(plays < g.plays) {
			return 1;
		}
		return -1;
	}
	public int getPlays() {
		return plays;
	}
	public void setPlays(int plays) {
		this.plays = plays;
	}
	public List<SongInfo> getSongInfo() {
		return songInfo;
	}
	public void setSongInfo(List<SongInfo> songInfo) {
		this.songInfo = songInfo;
	}
}
// 개별 노래정보 
class SongInfo {
	private int cntPlays; //조회수 
	private int index;	//인덱스 
	
	
	
	public SongInfo(int cntPlays, int index) {
		super();
		this.cntPlays = cntPlays;
		this.index = index;
	}
	
	public int getCntPlays() {
		return cntPlays;
	}
	public void setCntPlays(int cntPlays) {
		this.cntPlays = cntPlays;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	
}

 

다시 보고 공부해야지