99클럽 코테 스터디 1일차 TIL - 해시

항해99 코테 스터디 1일차 문제인 프로그래머스의 '베스트앨범'은 해시 자료구조를 이용하여 각 장르의 노래들을 최대 2곡씩 베스트 앨범에 수록하는 문제다. 난이도는 레벨3이며 자바의 HashMap을 통해 해결할 수 있다.

 

오늘의 문제 - 베스트앨범 문제 정보

문제 키워드

- 해시

난이도

- Level 3

 

문제 요약

• 두개의 리스트로 i번째 노래의 장르 이름과, i번째 노래의 재생횟수가 주어진다.
• 베스트앨범은 각 장르별 최대 2곡씩을 아래의 우선순위에 따라 수록하게 된다.
  1. 많이 재생된 장르 먼저 수록
  2. 장르별로 최대 2개, 많이 재생된 순서로 수록
  3. 장르 내에서 재생수가 같으면 고유번호 순서로 수록
• 베스트앨범에 수록된 곡들의 고유번호 리스트를 반환하라.

 

문제 풀이 과정  

• Song이라는 이름의 클래스를 만들어 노래의 고유 번호와 재생횟수를 담도록 했다. 또한 재생횟수가 많은 순, 고유번호가 빠른 순으로 정렬할 수 있도록 Comparable 인터페이스를 구현하였다.
• 장르별로 노래를 묶는데, 이 때 노래에 필요한 정보들을 함께 저장해야 한다.
  • 따라서 앞서 구현한 Song의 리스트를 저장하는 songInGenres Map과, 장르별 총 재생횟수를 가지고 있을 playInGenres Map을 정의하였다.
  • 노래 i개 각각에 대해 장르명을 이용해서 두 Map에 정보를 저장한다.
• 장르별로 노래들 및 총 재생횟수가 구해졌으니, 이제 베스트앨범에 수록할 곡을 선택하면 된다.
  • 먼저, 장르를 총 재생횟수가 많은 순서대로 정렬하여 구한다.
  • 정렬된 장르별로, 장르 내의 노래들 중 우선순위(많이 재생된 순, 고유번호 빠른 순)대로 정렬하여 구한다.
  • 장르별로 최대 2개까지만 정답 배열에 추가한다.

코드

import java.util.*;

class Solution {
    public List<Integer> solution(String[] genres, int[] plays) {
        
        // 1. 많이 재생된 장르 먼저 수록
        // 2. 장르별로 최대 2개, 많이 재생된 순서로 수록
        // 3. 장르 내에서 재생수가 같으면 고유번호 순서로 수록
        
        // 장르별로 노래 및 총 재생수를 Map에 저장
        Map<String, List<Song>> songInGenres = new HashMap<>();
        Map<String, Integer> playInGenres = new HashMap<>();
        
        for(int i=0; i < genres.length; i++) {
            String genre = genres[i];
            // 장르별 노래 저장
            songInGenres.putIfAbsent(genre, new ArrayList<>());
            Song newSong = new Song(i, plays[i]);
            songInGenres.get(genre).add(newSong);
            
            // 장르별 총 재생수 갱신
            playInGenres.putIfAbsent(genre, 0);
            playInGenres.put(genre, playInGenres.get(genre) + plays[i]);
        }
        
        // 장르명을 총 재생수가 많은 순으로 정렬
        List<String> genreNames = new ArrayList<>(playInGenres.keySet());
        genreNames.sort((o1, o2) -> playInGenres.get(o2).compareTo(playInGenres.get(o1)));
        
        // 각 장르의 노래들을 정렬 후 최대 2곡 선택하기
        List<Integer> answerList = new ArrayList<>();
        for(String genre: genreNames) {
            List<Song> songs = songInGenres.get(genre);
            Collections.sort(songs);
            for(int i=0; i < Integer.min(2, songs.size()); i++) {
                answerList.add(songs.get(i).songNo);
            }
        }
        
        return answerList;
    }
    
    class Song implements Comparable<Song> {
        int songNo;
        int playCnt;
        
        public Song(int songNo, int playCnt) {
            this.songNo = songNo;
            this.playCnt = playCnt;
        }
        
        @Override
        public int compareTo(Song other) {
            if (this.playCnt == other.playCnt) {
                return this.songNo - other.songNo;
            }
            return other.playCnt - this.playCnt;
        }
    }
}

• 시간복잡도: O(NlogN) -> 정렬
• 공간복잡도: O(N) -> Map 생성

 

오늘의 학습 회고

새롭게 알게된 것

• 프로그래머스에 정답을 제출할 때 자료형을 int[]에서 List<Integer>로 바꾸어도 정답으로 인정 된다..!
  • 그렇지만 꼭 int[]로 반환해야 되는 경우도 있으니 list.stream().mapToInt(i -> i).toArray() 도 기억하고 있자.
• Comparable로 compareTo() 구현할 때 오름/내림차순 헷갈리지 않게 주의하자.
  • 이 문제에서는 각 장르 내에서 재생횟수가 "많은 순"으로 정렬이 필요했다.

내일 학습할 것

• Java에서 해시 관련 자료형들을 더 자세하게 알아봐야겠다.