티스토리 뷰

프로그래머스 (programmers) 코딩테스트 고득점 Kit 해시 #4 - 베스트앨범

1. 문제 설명

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

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.


속한 노래가 많이 재생된 장르를 먼저 수록합니다.

장르 내에서 많이 재생된 노래를 먼저 수록합니다.

장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.


2. 제한사항

genres[i]는 고유번호가 i인 노래의 장르입니다.

plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.

genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.

장르 종류는 100개 미만입니다.

장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.

모든 장르는 재생된 횟수가 다릅니다.


3. 입출력 예


4. 입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.


고유 번호 3: 800회 재생

고유 번호 0: 500회 재생

고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.


고유 번호 4: 2,500회 재생

고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.


5. 나의 풀이 (알고리즘 해설)


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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
 
// 고유 번호(idx)와 재생 횟수(plays)를 가진 Song 클래스 생성
public class Song implements Comparable<Song> {
    public int idx;
    public int plays;
    public Song(int idx, int plays) {
        this.idx = idx;
        this.plays = plays;
    }
 
    //재생 횟수(plays) 큰 것이 더 크도록, 재생 횟수가 같다면 idx를 비교하여 더 낮은 것이 크도록 설정
    @Override
    public int compareTo(Song o) {
        if (this.plays == o.plays) {
            if (this.idx > o.idx) {
                return 1;
            } else {
                return -1;
            }
        } else if (this.plays < o.plays) {
            return 1;
        } else {
            return -1;
        }
    }
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        //장르의 순위 결정을 위한 Hash 생성
        HashMap<String, Integer> rankHash = new HashMap<String, Integer>();
        for (int i = 0; i < plays.length; i++) {
            rankHash.put(genres[i], rankHash.getOrDefault(genres[i], 0+ plays[i]);
        }
        
        //장르 순위 판별을 위한 우선순위 큐 생성 (java에서 int형 우선순위 큐는 작은 것 부터 나오므로 lamda식을 이용해 역순으로 변환)
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> y - x);
        for (Integer value : rankHash.values()) {
            pq.add(value);
        }
        
        //모든 장르는 재생된 횟수가 다르므로 rankHash의 Key, Value를 바꾼 HashMap 생성
        HashMap<Integer, String> rankHashReverse = new HashMap<Integer, String>();
        for (String key : rankHash.keySet()) {
            rankHashReverse.put(rankHash.get(key), key);
        }
 
        //장르의 재생 횟수를 이용하여 가장 높은 장르부터 rankArr에 순서대로 저장(장르의 순위 선정 완료)
        int uniqueGenreLength = pq.size();
        String[] rankArr = new String[uniqueGenreLength];
        for (int i = 0; i < uniqueGenreLength; i++) {
            rankArr[i] = rankHashReverse.get(pq.poll());
        }
        
        
        //장르의 순위는 정해졌으니 각 노래의 1,2위를 뽑기 위한 HashMap 생성
        HashMap<String, PriorityQueue<Song>> songsRank = new HashMap<String, PriorityQueue<Song>>();
        for (int i = 0; i < plays.length; i++) {
            if (songsRank.containsKey(genres[i])) {
                songsRank.get(genres[i]).add(new Song(i, plays[i]));
            } else {
                songsRank.put(genres[i], new PriorityQueue<Song>());
                songsRank.get(genres[i]).add(new Song(i, plays[i]));
            }
        }
        
        //정답리스트를 만들고 rankArr에 저장한 장르 순서대로 우선순위 큐에서 우선 순위가 높은 Song 하나씩 뽑아서 idx 저장
        ArrayList<Integer> answerArrList = new ArrayList<Integer>();
        for (int i = 0; i < rankArr.length; i++) {
            answerArrList.add(songsRank.get(rankArr[i]).poll().idx);
            //해당 장르에 한 곡이 전부라면 if 문 통과
            if (songsRank.get(rankArr[i]).peek() != null) {
                answerArrList.add(songsRank.get(rankArr[i]).poll().idx);
            }
        }
        
        //정답 리스트를 Array 형태로 변환 .toArray()는 Object[] 형태로 나오므로 int[] 형태로 바꾸어줌
        int[] answerArr = new int[answerArrList.size()];
        Object[] answerArrObj = answerArrList.toArray();
        for (int i = 0; i < answerArrObj.length; i++) {
            answerArr[i] = (int) answerArrObj[i];
        }
        
        return answerArr;
    }
}
cs

처음 보았을때는 쉬울 것 같지만 Hash, 정렬을 모두 활용해야 하는 까다로운 문제였습니다.
재생 횟수의 합이 높은 장르 순으로 [고유 번호, 재생 횟수]를 모두 고려하여 곡의 순위를 선정해야하는 문제입니다.

(line 32 ~ 55)
먼저 장르 순위를 HashMap을 이용하여 합산하고 HashMap의 Key와 Value를 뒤집어서 가장 재생 횟수의 합이 높은 장르부터 String[] rankArr에 저장하였습니다.

(line 58 ~ 67)
그 후 HashMap에 우선 순위 큐(priority queue)를 활용하여, 문제의 조건에 맞게 Comparable을 구현 해둔 Song 클래스(line 8 ~ 31}를 저장하는 방식으로 정렬을 하였습니다.

(line 69 ~ 77)
장르 순위 배열(rankArr)과 정렬된 HashMap(songsRank)을 만들었으므로 ArrayList에 장르 순위대로 2개씩 (1개뿐이라면 1개만) 담아줍니다.

(line 79 ~ 86)
ArrayList를 int 배열로 변환하여 return합니다.

6. 배운 점

- 고려할 것이 많을때는 Class를 만들어 Comparable로 구현하면 간단하게 해결할 수 있다는 것을 느꼈습니다.


- java의 우선 순위 큐를 활용하면 integer를 저장할때 숫자가 큰 순서대로 저장될 줄 알았는데 작은 순서대로 저장되었습니다. 따라서 역순으로 정렬하는 방법을 찾아보았더니 다양한 방법이 있었습니다. 제가 풀이에 사용한 방법은 긴 숫자를 연산시 overflow가 발생할 수 있기 때문에 Collections.reverseOrder()를 더 권장한다고 합니다. 그리고 우선순위큐는 배열에 기반한 자료구조이기 때문에 initial capacity를 설정하지 않으면 자동으로 11이 된다고하니 크기를 예상할 수 있는 부분이 있으면 설정하는 것이 더 효율적이겠습니다. (https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue)


- HashMap의 Key와 Value를 바꾸는 방법을 고민해 보았는데 검색해보니 iterator등을 복잡하게 활용하는 것들이 있었는데 그것 보다는 향상된 for 문을 활용하면 아주 간단한게 Key/Value 값을 교환할 수 있었습니다. (단, 여기서는 문제에 재생 횟수가 같은 장르는 없다고 하였으니 가능하지만, 재생 횟수가 겹치는 장르가 있다면 Key 값이 중복되어 교환 불가)

1
2
3
4
5
6
HashMap<String, Integer> rankHash = new HashMap<String, Integer>();
 
HashMap<Integer, String> rankHashReverse = new HashMap<Integer, String>();
for (String key : rankHash.keySet()) {
    rankHashReverse.put(rankHash.get(key), key);
}
cs


- 지난번 해시#1에서 다음에 활용해야겠다고 생각한 getOrDefault()를 활용하여 if else문을 줄일 수 있어서 더욱 편리하였습니다.

댓글