[Java/프로그래머스/해시] Level 3: 베스트앨범

문제

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

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

 

코드

롸... 진짜 너무 어렵잖응ㅁ..ㅠㅠㅠㅠㅠㅠ

어떤 자료구조를 쓸 지 고르는 것이 정말 어려웠다. (근데 이게 핵심임)

 

순서는 다음과 같다.

1. id(고유번호), play(재생횟수), genre를 담은 Song 객체를 만든다.

Song 객체는 ArrayList에 삽입한다. 동시에 각 장르별 play를 합산해 HashMap에 기록해준다.

2. 정렬

3. 정렬된 ArrayList를 바탕으로 베스트앨범 수록곡을 선정한다. 이때 장르별 2곡이라는 기준을 만족하기 위해 HashMap으로 장르별 수록곡 수를 저장한다.

 

import java.util.*;

class Song {
    int id, play;
    String genre;
    
    Song(int id, int play, String genre){
        this.id = id;
        this.play = play;
        this.genre = genre;
    }
}

class Solution {
    ArrayList<Integer> bestAlbum; //베스트 앨범 수록곡
    ArrayList<Song> songList; //노래 정보를 담은 ArrayList
    HashMap<String, Integer> genreMap; //장르와 총 play 수를 담은 HashMap(Key-value)
    HashMap<String, Integer> albumMap; //장르별 2곡 기준을 위한 HashMap
    
    public int[] solution(String[] genres, int[] plays) {
        bestAlbum = new ArrayList<>();
        songList = new ArrayList<>();
        genreMap = new HashMap<>();
        albumMap = new HashMap<>();
        
        //1. Song 객체를 ArrayList(songList)에 삽입한다.
        //동시에 각 장르별 play를 합산해 HashMap(genreMap)에 기록해준다.
        for(int i=0; i<genres.length; i++){
            int id =i;
            int play = plays[i];
            String genre = genres[i];
            
            //노래 정보(id, play, genre)를 담아준다.            
            songList.add(new Song(id, play, genre));
            
            //genreMap에 이미 있는 장르라면
            if(genreMap.containsKey(genre)){
                genreMap.put(genre, genreMap.get(genre)+play); //원래 있는 play 횟수에 해당 노래의 play 횟수를 더해준다.
            }else{
                genreMap.put(genre, play); //새로 만듦
            }
        }
        
        //2. 정렬 (기준 : 속한 노래가 많은 장르 먼저 -> 장르 내에서는 많이 재생된 노래 먼저 -> 장르 내에서 재생 횟수가 같으면 고유 번호가 낮은 것부터)
        Collections.sort(songList, (s1, s2) -> {
            //장르가 같은 경우
            if(s1.genre.equals(s2.genre)){
                //플레이 횟수가 같은 경우
                if(s1.play == s2.play)
                    return s1.id-s2.id; //고유번호가 작은 것부터
                else
                    return s2.play-s1.play; //플레이 횟수가 큰 것부터
            }else{
                return genreMap.get(s2.genre) - genreMap.get(s1.genre);//장르의 총 플레이 횟수가 큰 것부터
            }
        });
        
        //3. 베스트앨범을 ArrayList(bestAlbum)에 수록. (장르별 2곡이라는 기준을 만족하기 위해 HashMap(albumMap)으로 장르별 수록곡 수를 저장한다.)
        for(Song song : songList){
            //albumMap에 없던 장르라면
            if(!albumMap.containsKey(song.genre)){
                albumMap.put(song.genre, 1); //Key인 장르와 Value인 1을 추가한다.
                bestAlbum.add(song.id); //수록
            }else{
                //해당 노래의 장르 내 순서
                int genreCnt = albumMap.get(song.genre); 
                
                if(genreCnt >= 2)
                    continue;
                else{
                    albumMap.put(song.genre, genreCnt + 1); //해당 장르 2
                    bestAlbum.add(song.id); //수록
                }
            }
        }
        
        int[] answer = new int[bestAlbum.size()];
        for(int i = 0 ; i < answer.length ; ++i){
            answer[i] = bestAlbum.get(i);
        }
        
        return answer;
    }
}