Today's Algorithm2(2019-01-07)

programmers. 베스트 앨범

문제 자체가 그렇게 복잡하진 않았습니다. 다만 자료구조를 어떻게 만들 것이고, 그리고 그 자료구조를 이용하여 어떻게 여러 정렬기준을 적용할 것인지가 문제의 관건이었던 것 같습니다. 저의 경우 객체를 2개를 만들었는데요. Gerne 와 Song 입니다. 그리고 Genre 안에 Song List가 있습니다. 여러 정렬 기준이 존재함에 따라 해당 상태값을 갖고 그것에 맞게 정렬할 수 있도록 해야했습니다. 정렬 기준은 다음과 같습니다.

가장 많이 재생된 장르순 > 장르내 가장 많이 재생된 노래순 > 재생 고유번호가 낮은 순

package p42579;

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Genre> map = new HashMap<>();
        Queue<Genre> queue = new PriorityQueue<>(Collections.reverseOrder());

        init(queue, genres, plays, map);  // map과 queue에 데이터 원하는데로 넣기

        while(!queue.isEmpty()){
            List<Song> songs = queue.poll().getSongs();
            Collections.sort(songs);  // 많이 재생된 노래 > 고유번호 낮은 순으로 정렬
            int index = 0;
            while(!songs.isEmpty() && index < 2) {  // 2개 이하만 고를 수 있도록 설정
                answer.add(songs.remove(0).getId());
                index++;
            }
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }

    private void init(Queue<Genre> queue, String[] genres, int[] plays, Map<String, Genre> map) {
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            Genre aGenre = map.getOrDefault(genre, new Genre(0, new ArrayList<>()));
            aGenre.add(new Song(i, plays[i]));
            map.put(genre, aGenre);
        }

        for (String s : map.keySet()) {
            queue.offer(map.get(s));
        }
    }
}

class Genre implements Comparable<Genre> {
    private int sumOfPlay;
    private List<Song> songs;

    public Genre(int sumOfPlay, List<Song> songs) {
        this.sumOfPlay = sumOfPlay;
        this.songs = songs;
    }

    public List<Song> getSongs() {
        return songs;
    }

    public void add(Song song) {
        this.sumOfPlay += song.getPlay();
        this.songs.add(song);
    }

    @Override
    public int compareTo(Genre o) {  // 재생수의 합에 따른 장르 정렬
        return this.sumOfPlay - o.sumOfPlay;
    }
}

class Song implements Comparable<Song> {
    private int id;
    private int play;

    public Song(int id, int play) {
        this.id = id;
        this.play = play;
    }

    public int getId() {
        return id;
    }

    public int getPlay() {
        return play;
    }

    @Override
    public int compareTo(Song o) {
        if(o.play - this.play == 0) {  // 가장 많이 재생된 수대로 정렬
            return this.id - o.id;     // 재생수가 같을 때 재생 고유번호가 낮은 순으로 정렬
        }
        return o.play - this.play;
    }
}

코드를 작성하고 작성 후 다른 사람들의 코드를 보면서 배운점을 정리해볼게요.

 

• 우선순위큐에서 수를 뽑을 때 foreach로 빼지 말것!!

  • 코드가 아무리봐도 맞는 것 같은데 계속 정답이 아니라고 나왔습니다. 분명 테스트케이스는 맞는데 말이죠.
  • 계속 보다 제가 PrioirtyQueue에서 수를 뽑을 때 foreach로 수를 꺼내고 있다는 것을 발견하게 되었습니다. 하지만 이렇게 뽑으면 제가 원하는 최대힙의 순서로 나오지 않는 문제가 발생합니다. while문과 poll()을 써야 제가 원하는대로 얻을 수 있습니다.

• Map에 수를 넣을 때 map.containsKey() 보다는 map.getOrDefault() 을 사용해보자

  • 혼자 코드를 짤 때 map.getOrDefault() 의 존재 자체를 몰랐습니다. 하지만 이를 사용하면 분기할 필요없이 key가 있으면 해당 value를 가져오고, key가 없으면 default로 설정해놓은 value값을 가져올 수 있었습니다.
  • 이를 통해 여러 중복 코드를 줄일 수 있었습니다. 하지만 낯선만큼 처음 사용할 때 실수를 하곤 했는데요. default값 설정하는 부분에 유념해서 사용해야 할 것 같습니다.