99클럽 3기 코테 스터디 5일차 TIL /[프로그래머스] 베스트앨범 자바 풀이, 해시

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

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

프로그래머스

 

 

 

문제 설명

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

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

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

 

 

---

 

 

 

 

 

 

코드

---

import java.util.*;

class Solution {
    /*
    해시맵생성,
    장르명: int[5] 배열
    [0]: 장르의 총 재생수
    [1]: 수록곡1의 플레이수
    [2]: 수록곡1의 고유번호
    [3]: 수록곡2의 플레이수
    [4]: 수록곡2의 고유번호
    반복문에서, 곡을 해당 장르의 수록곡1, 2와 재생횟수를 비교하여 배열 갱신

    반복문종료: 최다재생수에 따라 고유번호 return


    */
    public int[] solution(String[] genres, int[] plays) {
        int[] answer ;

        HashMap<String, Integer[]> map =new HashMap<>();

        for(int i=0;i< genres.length; i++){

            if(!map.containsKey(genres[i])){//맵에 장르가 없으면 추가해줌
                Integer[] initialArray = new Integer[5];
                Arrays.fill(initialArray, 0); // 배열을 0으로 초기화
                map.put(genres[i], initialArray);

                map.get(genres[i])[1]=plays[i]; //플레이수
                map.get(genres[i])[2]=i; // 고유번호
            }

            //맵에 장르가 있고, 2번째 삽입인 경우
            else if(map.get(genres[i])[3]==null){

                map.get(genres[i])[3]=plays[i]; //플레이수
                map.get(genres[i])[4]=i; // 고유번호
            }

            //맵에 장르가 있고, 3번째 이상 비교
            else{
                int minPlay=0; //두 곡 중 더 작은 플레이수와 인덱스를 저장
                int minIdx=0;
                if(map.get(genres[i])[1]>map.get(genres[i])[3]){
                    minPlay=map.get(genres[i])[3];
                    minIdx=3;
                }
                else{
                    minPlay=map.get(genres[i])[1];
                    minIdx=1;
                }

                if(plays[i]> minPlay){ //현재 플레이수와 비교해서, 현재 플레이수가 더 크다면 갱신
                    map.get(genres[i])[minIdx]=plays[i];
                    map.get(genres[i])[minIdx+1]=i;
                }

            }

            map.get(genres[i])[0]+=plays[i]; //총 재생수 더해줌


        }

        List<Map.Entry<String, Integer[]>> list = new ArrayList<>(map.entrySet()); //키들을 리스트로 가져옴

        
          list.sort(new Comparator<Map.Entry<String, Integer[]>>() {
            @Override
            public int compare(Map.Entry<String, Integer[]> entry1, Map.Entry<String, Integer[]> entry2) {
                // 내림차순 정렬을 위해 비교 결과를 반전
                return entry2.getValue()[0].compareTo(entry1.getValue()[0]);
            }
        });
        
        
        ArrayList<Integer> arrayList =new ArrayList<>();
        
        for (Map.Entry<String, Integer[]> entry : list) {
            Integer[] array= entry.getValue();
            int min=4;
            int max=2; //먼저 출력할 인덱스 
            
            if(array[3]==0 ){ //하나의 곡만 들어있을 때
                arrayList.add(array[max]);
                continue;
            }
            
            if(array[1].equals(array[3])){ //플레이회수같다면 
                if(array[2]>array[4]){
                    min=2; max=4;
                }
            }
            else if(array[1]<array[3]){ // arary3이 더 크면
                min=2; max=4;
            }
            arrayList.add(array[max]);
            arrayList.add(array[min]);
        }
        
        answer=new int[arrayList.size()];
        int size=0;
        for(int temp:arrayList){
            answer[size++]=temp;
        }
        
        
        return answer;
    }

}

 

 

해시맵을 생성해

장르명 string: int[5]배열을 넣어준다

[0]	[1]	[2][	[3]	[4]
총 재생횟수	수록곡1 재생횟수	수록곡1 고유번호	수록곡2 재생횟수	수록곡2 고유번호

 

배열에는 위와같은 형태로, 장르에 대한 총 재생횟수와 장르내에서 수록할 곡 2개를 넣어준다. 

첫번째 for문에서 geners의 크기만큼 반복하여 해시맵을 만들어준다. 

 

다음으로, 해시맵을 밸류의 [0]번 인덱스(총 재생횟수)에 대해 키를 내림차순 정렬해준다

 

정렬한 키에 대해, entry에서 수록곡을 조건에 맞게 arrayList에 담아준다. 

 

arrayList를 배열로 바꿔줘 return하면 성공 

2. 오늘의 회고

---

 

• 문제를 다소 더럽게 푼 것 같다

 

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 장르별 정보를 저장할 해시맵
        HashMap<String, GenreInfo> genreMap = new HashMap<>();
        
        // 장르별 곡 정보를 업데이트
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int playCount = plays[i];
            
            genreMap.putIfAbsent(genre, new GenreInfo());
            GenreInfo info = genreMap.get(genre);
            
            info.totalPlayCount += playCount;
            info.addSong(playCount, i);
        }
        
        // 장르별 총 재생수에 따라 내림차순 정렬
        List<Map.Entry<String, GenreInfo>> genreList = new ArrayList<>(genreMap.entrySet());
        genreList.sort((e1, e2) -> Integer.compare(e2.getValue().totalPlayCount, e1.getValue().totalPlayCount));
        
        // 결과를 저장할 리스트
        List<Integer> result = new ArrayList<>();
        
        for (Map.Entry<String, GenreInfo> entry : genreList) {
            GenreInfo info = entry.getValue();
            result.addAll(info.getTopTwoSongs());
        }
        
        // 결과 리스트를 배열로 변환
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
    
    // 장르 정보를 저장할 클래스
    private static class GenreInfo {
        int totalPlayCount = 0;
        int[] songPlayCounts = new int[2];
        int[] songIndices = new int[2];
        
        //songPlayCounts에 크기순으로 들어가게 됨. 
        void addSong(int playCount, int index) {
            if (songPlayCounts[0] < playCount) {
                songPlayCounts[1] = songPlayCounts[0];
                songIndices[1] = songIndices[0];
                songPlayCounts[0] = playCount;
                songIndices[0] = index;
            } else if (songPlayCounts[1] < playCount) {
                songPlayCounts[1] = playCount;
                songIndices[1] = index;
            }
        }
        
        List<Integer> getTopTwoSongs() {
            List<Integer> topSongs = new ArrayList<>();
            if (songPlayCounts[0] > 0) topSongs.add(songIndices[0]);
            if (songPlayCounts[1] > 0) topSongs.add(songIndices[1]);
            return topSongs;
        }
    }
}

 

풀이 참고해 리팩토링한 코드.

클래스를 만드니 깔끔

 

map.putIfAbsent () :  Key 값이 존재하는 경우 Map의 Value의 값을 반환하고, Key값이 존재하지 않는 경우 Key와 Value를 Map에 저장하고 Null을 반환한다.

 

해시맵에 string장르명: GenerInfo 클래스를 넣었다.

클래스 넣어서 addSong메서드로 크기순으로 항상 정렬되게 관리하고,

getTopTwoSongs 메서드는 수록곡들을 반환

 

map의 entry란, 맵에 저장된 키-값 쌍을 나타낸다. Map.entry 인터페이스로 엔트리를 표현한다. 

getKey(), getValue()메서드를 제공한다. 

쉽게 말해 맵에 저장된 키-값 쌍을 다루는 인터페이스! 

 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL