베스트앨범(PG_LV3_42579)

1. 문제 링크

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

프로그래머스

---

 

2. 나의 코드

메모리: 76.1MB
시간: 1.30ms
코드 길이: B
시간 복잡도 : O(NlogN)
설명
- Map을 사용하여 각각의 장르별 재생수의 합을 저장
- Map을 사용해서 각각의 장르별 key값에 인덱스와 플레이 수가 들어간 리스트를 추가
- 정렬을 사용하여 2번까지 배열에 담기

import java.util.*;

class Solution {
    static class music implements Comparable<music>{
        int idx, playCnt;
        public music(int idx, int playCnt) {
            this.idx = idx;
            this.playCnt = playCnt;
        }
        @Override
        public int compareTo(music o) {
            if (this.playCnt != o.playCnt) return o.playCnt - this.playCnt;
            return this.idx - o.idx;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        List<Integer> result = new ArrayList<>();
        Map<String, Integer> musicCnt = new HashMap<>();
        Map<String, List<music>> musics = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            if(!musicCnt.containsKey(genres[i])) {
                musicCnt.put(genres[i], plays[i]);
            } else {
                int newCnt = musicCnt.get(genres[i]) + plays[i];
                musicCnt.put(genres[i], newCnt);
            }
            if (!musics.containsKey(genres[i])) {
                musics.put(genres[i], new ArrayList<>());
            }
            musics.get(genres[i]).add(new music(i, plays[i]));
        }

        List<String> keySet = new ArrayList<>(musicCnt.keySet());
        keySet.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return musicCnt.get(o2).compareTo(musicCnt.get(o1));
            }
        });
        for (String g : keySet) {
            Collections.sort(musics.get(g));
            if (musics.get(g).size() == 1) {
                result.add(musics.get(g).get(0).idx);
            }
            else {
                for (int i = 0; i < 2; i++) {
                result.add(musics.get(g).get(i).idx);
                }
            }
        }
        answer = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }
        return answer;
    }
}

 

---

 

3. 정답 코드

class Solution {  
	
	// 노래의 번호와 재생 횟수를 담는 클래스
    static class Song implements Comparable<Song> {
        int no, playCnt;
        
        Song(int no, int playCnt) {
            this.no = no;
            this.playCnt = playCnt;
        }
        
        @Override
        public int compareTo(Song o) {
            if (this.playCnt == o.playCnt) {
                return this.no - o.no;
            }
            return o.playCnt - this.playCnt;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        int[] answer;
        List<Integer> answerNos = new ArrayList<>(); // 정답 변환용 리스트
        Map<String, List<Song>> map = new HashMap<>();  // 장르별 노래 정보를 담는 맵
        Map<String, Integer> playCntMap = new HashMap<>(); // 장르별 총 재생 횟수를 담는 맵
        List<Map.Entry<String, Integer>> list; // 장르별 총 재생 횟수를 담는 리스트
        
        // 초기 세팅
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int playCnt = plays[i];
            
            if (!map.containsKey(genre)) {
                map.put(genre, new ArrayList<>());
            }
            List<Song> songs = map.get(genre);
            songs.add(new Song(i, playCnt));
            
            playCntMap.put(genre, playCntMap.getOrDefault(genre, 0) + playCnt);
        }
        
        // 장르별 재생횟수를 기준으로 오름차순 정렬
        list = new ArrayList<>(playCntMap.entrySet());
        Collections.sort(list, Map.Entry.comparingByValue());
        
        // 재생횟수가 높은 장르부터 탐색
        for (int idx = list.size() - 1; idx >= 0; idx--) {
            Map.Entry<String, Integer> entry = list.get(idx);
            List<Song> selectedSongs = map.get(entry.getKey());
            Collections.sort(selectedSongs);
            int cnt = 0;
            
            // 기준에 맞는 노래 최대 두개를 정답 리스트에 넣기
            for (int i = 0; i < selectedSongs.size(); i++) {
                Song song = selectedSongs.get(i);
                answerNos.add(song.no);
                cnt++;
                if (cnt == 2) {
                    break;
                }
            }
        }
        
        answer = answerNos.stream().mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
}

 

 

---

 

4. 배운 점

- Map을 사용하는 방법을 더욱더 공부해야겠다.

- 값 저장은 put, 값 조회는 get, ".keySet()"을 하면 key값 리스트가 나온다.