프로그래머스 42579번 베스트앨범

문제

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

풀이

예전에 푼 문제를 다시 풀었는데, 예전의 풀이(풀이1)가 더 성능이 좋았다.

풀이1 : 장르별로 묶어서 장르 내에서 각각 sorting 후 장르별로 상위2개씩 return

풀이2 : 장르에 대한 총 재생수만 hashmap으로 저장 후, 전체 sorting, 장르별로 상위2개씩 return

풀이1

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

class Solution {
    class Genre {
		int sum;
		ArrayList<Pair> list;
		Genre(int sum, ArrayList<Pair> list) {
			this.sum = sum;
			this.list = list;
		}
		public void add(Pair p) {
			this.sum += p.plays;
			this.list.add(p);
		}
	}
	class Pair {
		int index;
		int plays;
		Pair(int index, int plays) {
			this.index = index;
			this.plays = plays;
		}
	}
	
	public int[] solution(String[] genres, int[] plays) {
		int[] answer = {};
		
		ArrayList<Genre> genreList = new ArrayList<Genre>();
		HashMap<String, Integer> genreMap = new HashMap<String, Integer>();
		int curIndex = 0;
		for(int i = 0; i < genres.length; ++i) {
			Integer index = genreMap.get(genres[i]);
			if(index == null) {
				genreMap.put(genres[i], curIndex++);
				Pair p = new Pair(i, plays[i]);
				ArrayList<Pair> list = new ArrayList<Pair>();
				list.add(p);
				Genre g = new Genre(plays[i], list);
				genreList.add(g);
			} else {
				Pair p = new Pair(i, plays[i]);
				Genre g = genreList.get(genreMap.get(genres[i]));
				g.add(p);
				genreList.set(index, g);
			}
		}
		//sort each List
		Collections.sort(genreList, new Comparator<Genre>() {
			@Override
			public int compare(Genre a, Genre b) {
				int suma = a.sum;
				int sumb = b.sum;
				if(suma < sumb) return 1;
				else if(suma > sumb) return -1;
				else return genres[a.list.get(0).index].compareTo(genres[b.list.get(0).index]);
			}
		});
		for(int i = 0; i < genreList.size(); ++i) {
			Genre g = genreList.get(i);
			ArrayList<Pair> l = g.list;
			Collections.sort(l, new Comparator<Pair> () {
				@Override
				public int compare(Pair a, Pair b) {
					if(a.plays < b.plays) return 1;
					else if(a.plays > b.plays) return -1;
					else {
						if(a.index < b.index) return -1;
						else if(a.index > b.index) return 1;
						else return 0;
					}
				}
			});
			g.list = l;
			genreList.set(i, g);
		}
		//printGl(genreList);
		ArrayList<Integer> answerAl = new ArrayList<Integer>();
		boolean flag = false;
		for(int i = 0; i < genreList.size(); ++i) {
			for(int j = 0; j < (genreList.get(i).list.size() >= 2 ? 2 : genreList.get(i).list.size()); ++j) {
				answerAl.add(genreList.get(i).list.get(j).index);
			}
		}
		return arrayListToArray(answerAl);
	}
	public int[] arrayListToArray(ArrayList<Integer> al) {
		int[] ret = new int[al.size()];
		for(int i = 0; i < al.size(); ++i) {
			ret[i] = al.get(i);
		}
		return ret;
	}
}

 

풀이2

import java.util.*;
class Solution {
    class Song {
        Integer id;
        String genre;
        Integer plays;
        Song(Integer id, String genre, Integer plays) {
            this.id = id;
            this.genre = genre;
            this.plays = plays;
        }
    }
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        HashMap<String, Integer> genreCount = new HashMap<String, Integer>();
        //sort이후에 원래값 찾기위해
        ArrayList<Song> arrayListSong = new ArrayList<Song>();
        
        for(int i = 0; i < genres.length; ++i) {
            //장르별 전체 재생수를 카운트
            if(genreCount.get(genres[i]) == null) {
                genreCount.put(genres[i], plays[i]);
            } else {
                genreCount.put(genres[i], genreCount.get(genres[i]) + plays[i]);
            }
            //sort를 위해 Song ArrayList에 push
            Song song = new Song(i, genres[i], plays[i]);
            arrayListSong.add(song);
        }
        
        Collections.sort(arrayListSong, new Comparator<Song>() {
            @Override
            public int compare(Song song1, Song song2) {
                //양수면 song1, 음수면 song2
                //1. 장르 총 재생수 비교
                if(genreCount.get(song1.genre) > genreCount.get(song2.genre)) return -1;
                else if(genreCount.get(song1.genre) < genreCount.get(song2.genre)) return 1;
                else {
                    //2. 장르 내에서 많이 재생된 노래
                    if(song1.plays > song2.plays) return -1;
                    else if(song1.plays < song2.plays) return 1;
                    else {
                        //3. 장르, 재생횟수가 같으면 고유번호가 낮은 노래 먼저
                        return song2.id - song1.id;
                    }
                }
            }
        });
        HashMap<String, Integer> answerCount = new HashMap<String, Integer>();
        ArrayList<Integer> answerArrayList = new ArrayList<Integer>();
        
        for(int i = 0; i < arrayListSong.size(); ++i) {
            //System.out.println(arrayListSong.get(i).id + ", " + arrayListSong.get(i).genre + ", " + arrayListSong.get(i).plays);
            Integer currentId = arrayListSong.get(i).id;
            if(answerCount.get(arrayListSong.get(i).genre) == null) {
                answerArrayList.add(currentId);
                answerCount.put(arrayListSong.get(i).genre, 1);
            } else if(answerCount.get(arrayListSong.get(i).genre) == 2) {
                continue;
            } else {
                answerArrayList.add(currentId);
                answerCount.put(arrayListSong.get(i).genre, answerCount.get(arrayListSong.get(i).genre) + 1);
            }
        }
        answer = new int[answerArrayList.size()];
        for(int i = 0; i < answerArrayList.size(); ++i) {
            answer[i] = answerArrayList.get(i);
        }
        return answer;
    }
}