99클럽 코테 스터디 5일차 TIL + HashMap/[프로그래머스] 베스트앨범

💡문제

[level 3] 베스트앨범 - 42579

문제 링크

성능 요약

메모리: 76.4 MB, 시간: 4.64 ms

---

 

🤔접근법

문제 요약

• 복잡한 우선순위에 맞춰 정렬한 다음 조건에 맞게 노래 번호를 출력하는 문제
• 우선순위 설명 (장르에 따른 우선순위 조건이 있고, 노래에 따른 우선순위 조건이 있다.)
  • 각 장르별로 재생 수를 합산하여 재생 수가 높은 순서대로 출력
  • 단, 각 장르별로 노래는 2개씩 출력한다. (만약 주어진 보기에 장르에 해당하는 노래가 한개라면 하나만 출력한다.)
  • 두 노래의 우선순위는 재생 수가 높은 것을 우선으로 출력, 단 재생수가 같다면 고유 번호가 낮은 순서로 출력

 

범위 체크 및 시간복잡도 예상

• 1 ≤ 노래 곡 수 ≤ 10,000
• 장르 종류는 100개 미만
• $O(노래곡수^2)$ 까지도 가능

 

풀이법

⭕ 접근 방법. 완탐

🔑 HashMap을 이용하여 각 장르별 합계를 만드는 과정을 줄이자!

1. (장르명) : (총재생수) 를 key와 value로 가지는 hashmap을 생성
2. (장르명) : (1순위노래, 2순위노래를 담은 객체) 를 key와 value로 가지는 hashmap 생성
3. 주어진 노래들의 장르와 재생수를 순회
4. 현재 차례의 장르명을 key 로 가지는 map요소가 존재하는지 확인
5. 존재하지 않는다면 두 map에 대하여 요소 생성
6. 존재한다면 총재생수는 더해주고, 1순위, 2순위로 저장해둔 노래와 비교하여 순위를 다시 매겨준다.
7. 다 반복하였다면 총 재생수를 value로 가지는 map을 list로 변환 후 value를 기준으로 내림차순으로 정렬
8. list를 순회하면서 장르별 1순위, 2순위 노래번호 or 1순위만 노래번호를 새로운 list에 담는다.

➡️ 해당 풀이법의 시간 복잡도 : $O(노래곡수 * 장르수 )$

 

 

---

😎SUCCESS

단박에 성공하지 못한 이유는 ?

• 1순위, 2순위를 비교하는 과정에서 1순위와 들어온 노래와 재생수가 같고, 1순위보다 노래번호가 클때 2순위와 한번더 비교 해야한다는 것을 간과하였다.
• 아무튼간에 노래 간의 우선순위를 계산하는 로직이 복잡하였다.
• 사실은 노래 번호와, 재생수를 변수로 가지는 객체가 있었다면 compareTo 사용하여 좀더 쉽게 할 수 있겠다는 생각이 나중에 들었다.
• 그리고 compareTo , comparable을 사용하는 방법을 까먹었다 ㅎㅎ
• 또 .. 맵을 list로 만드는 법도 새로웠다. entrySet

---

👩‍💻 코드

import java.util.*;

class Solution {
        public class Album{
            int first;
            int seconds;

            public Album(int num) {
                first = num;
                seconds = -1;
            }
            public int compare(int n1, int n2, int[] plays){
                if(plays[n1] == plays[n2]){ // 재생수가 같다면 번호가 작은게 우선
                    return n2 - n1; // 양수면 n2가 숫자가 더 크니까 n1이 더 우선, 음수면 n1이 숫자가 더 크니까 n2가 더 우선
                }
                //재생수가 큰게 우선
                return plays[n1] - plays[n2]; //양수면 n1재생수가 더 크니까 n1이 우선, 음수면 n2재생수가 더 크니까 n2가 우선
            }
            public void reorder(int num, int plays[]){
                int temp;
                if(compare(first, num, plays) <  0){
                    // 음수면 num이 1위
                    temp = first;
                    first = num;
                }else{
                    // 양수면 first가 그대로 1위
                    temp = num;
                }

                if(seconds == -1){ // 2위 자리 비어 있으면 넣고 마치기
                    seconds = temp;
                    return;
                }

                if(compare(seconds, temp, plays) <  0){
                    // 음수면 temp 2위
                    seconds = temp;
                    // 양수면 seconds가 그대로 2위
                }
            }
        }
    public int[] solution(String[] genres, int[] plays) {
            HashMap <String, Integer> bestAlbumPlay = new HashMap<>();
            HashMap <String, Album> bestAlbum = new HashMap<>();

            for (int i = 0; i < genres.length; i++) {
                if(bestAlbumPlay.containsKey(genres[i])){ // 기존에 있던 장르
                    // 재생수 합하고
                    bestAlbumPlay.put(genres[i], bestAlbumPlay.get(genres[i]) + plays[i]);

                    // 순서 다시 정하기
                    bestAlbum.get(genres[i]).reorder(i, plays);

                }else{ // 새로운 장르
                    // 재생수 map에 추가
                    bestAlbumPlay.put(genres[i], plays[i]);

                    // 순서 map에 생성
                    bestAlbum.put(genres[i], new Album(i));
                }
            }

            List<Map.Entry<String ,Integer>> list = new ArrayList<>(bestAlbumPlay.entrySet());
            list.sort(Map.Entry.comparingByValue((o1, o2) -> o2-o1));

            ArrayList<Integer> answer = new ArrayList<>();
            for (int i = 0; i < bestAlbumPlay.size(); i++) {
                Album album = bestAlbum.get(list.get(i).getKey());
                answer.add(album.first);
                if(album.seconds != -1){
                    answer.add(album.seconds);
                }

            }
            int result[] = new int[answer.size()];
            for (int i = 0; i < result.length; i++) {
                result[i] = answer.get(i);
            }
            return result;
    }
}

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