알고리즘 풀이/프로그래머스

프로그래머스 - 베스트앨범 (해시)

배게 2019. 12. 3. 07:03
728x90

해시, 우선순위큐 사용, 


Genre라는 class만들어줘서 문제에서 주어진 총재생시간, 재생시간가장Top1,2의 index를 활용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
    public int[] solution(String[] genres, int[] plays) {
        int[] answer;
        ArrayList<Integer> answerList = new ArrayList<>();
 
        HashMap<String, Genre> hm = new HashMap<>();
 
        for (int i = 0; i < plays.length; i++) {
            // System.out.println(i+" "+genres[i]+" "+plays[i]);
            if (!hm.containsKey(genres[i])) {
                hm.put(genres[i], new Genre(genres[i]));
            }
 
            Genre nowGenre = hm.get(genres[i]);
            nowGenre.addSong(i, plays[i]);
 
            hm.put(genres[i], nowGenre);
        }
 
        PriorityQueue<Genre> pq = new PriorityQueue<>();
        // System.out.println();
        for (String key : hm.keySet()) {
            // System.out.println(hm.get(key));
            pq.add(hm.get(key));
        }
 
        // System.out.println();
        while (!pq.isEmpty()) {
            Genre nowGenre = pq.poll();
            // System.out.println(nowGenre);
 
            if (nowGenre.mostPlayedIndex[0] != -1)
                answerList.add(nowGenre.mostPlayedIndex[0]);
            if (nowGenre.mostPlayedIndex[1] != -1)
                answerList.add(nowGenre.mostPlayedIndex[1]);
 
        }
 
        // System.out.println(answerList.size());
 
        answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
 
        // pq사용해서 총 playtime긴 순서대로의 장르를 먼저 빼옴..
 
        return answer;
    }
 
    class Genre implements Comparable<Genre> {
        String genre;
        int[] mostPlayedIndex;
        int[] mostPlayedTime;
        int totalPlayTime;
 
        Genre(String genre) {
            this.genre = genre;
            mostPlayedIndex = new int[2];
            mostPlayedTime = new int[2];
            Arrays.fill(mostPlayedIndex, -1);
            Arrays.fill(mostPlayedTime, -100);
            totalPlayTime = 0;
        }
 
        void addSong(int idx, int playTime) {
            totalPlayTime += playTime;
 
            if (playTime > mostPlayedTime[0]) {
                mostPlayedTime[1] = mostPlayedTime[0];
                mostPlayedTime[0] = playTime;
 
                mostPlayedIndex[1] = mostPlayedIndex[0];
                mostPlayedIndex[0] = idx;
 
            } else if (playTime > mostPlayedTime[1]) {
                mostPlayedTime[1] = playTime;
                mostPlayedIndex[1] = idx;
            }
 
        }
 
        public String toString() {
            return genre + " " + mostPlayedIndex[0] + " " + mostPlayedIndex[1] + " " + totalPlayTime;
        }
 
        @Override
        public int compareTo(Genre g) {
            return Integer.compare(g.totalPlayTime, this.totalPlayTime);
        }
 
    }
cs


저작자표시