99클럽 코테 스터디 5일차 TIL

오늘의 학습 키워드

• 정렬
• 구현

문제

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

나의 풀이

1. 1차 풀이

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> genreMap = new HashMap<>();
        HashMap<String, List<Integer>> playMap = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            Integer prevPlays = genreMap.getOrDefault(genres[i], 0);
            genreMap.put(genres[i], prevPlays + plays[i]);
            if (playMap.containsKey(genres[i])) {
                if (prevPlays > plays[i]) {
                    playMap.get(genres[i]).add(i);
                } else {
                    playMap.get(genres[i]).add(0, i);
                }
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                playMap.put(genres[i], list);
            }
        }

        genreMap.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .forEach(entry -> {
                    List<Integer> integers = playMap.get(entry.getKey());
                    answer.addAll(integers.subList(0, Math.min(1, integers.size())));
                });
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

• 예시는 통과 했으나 체점하기에서 실패한 케이스
• 생각해보니 , prevPlays 비교부분에 이렇게 비교하면 3번째부터는 정상적으로 정렬이 되지 않을 것으로 보임.

1. 2차 풀이

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> genreMap = new HashMap<>();
        HashMap<String, List<Integer[]>> playMap = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            genreMap.put(genres[i], genreMap.getOrDefault(genres[i], 0) + plays[i]);

            if (!playMap.containsKey(genres[i])) {
                playMap.put(genres[i], new ArrayList<>());
            }
            playMap.get(genres[i]).add(new Integer[]{i, plays[i]});
        }

        genreMap.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .forEach(entry -> {
                    List<Integer[]> songs = playMap.get(entry.getKey());
                    songs.sort((a, b) -> b[1] - a[1]);
                    
                    for (int i = 0; i < Math.min(2, songs.size()); i++) {
                        answer.add(songs.get(i)[0]);
                    }
                });
        
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

• 이전 값을 비교해서 리스트에 넣는 로직을 제거하고, 노래의 인덱스와 플레이 수를 그대로 배열에 넣었다.
• 이후 장르의 총합을 저장한 맵을 역순으로 정렬한 후, 노래와 인덱스가 들어있는 배열을 다시 곡수 대로 정렬한다.
• 정렬한 노래 배열에서 최대 2곡까지 정답에 추가한다.

오늘의 회고

• 오늘 문제도 구현 문제였다. 노래 곡수가 최대 10000곡, 장르 종류가 100곡이여서 시간적으로는 여유있는 문제였다.
• 의사코드를 먼저 작성하고 코딩하는 습관이 필요할 듯 하다.
• 미리 의사코드를 작성하고 진행했으면, 비교구문이 틀린 것을 미리 알 수 있었을 것이다.