프로그래머스 베스트 앨범

작성일 | In |

Problem : 베스트 앨범

유형 : 해싱

문제 해석

  • 장르별에서 가장 많이 재생된 노래 두개씩을 뽑아라.

문제 재해석

  • 가장 많이 재생된 장르를 고른다.
  • 장르 내에서 가장 많이 재생된 노래를 고른다.
  • 장르 내에서 가장 많이 재생된 노래가 여러 개라면, 낮은 고유 번호의 노래를 고른다.

해결 전략

  • 장르가 뭐가 나올지 모른다. 해싱을 이용한다.
  • 노래 개수는 1만개가 넘지 않는다. 장르 종류도 100개 이하이다.
  • 모든 장르는 재생된 횟수가 다르다 는 점을 캐치 한다.
  • 장르 이름에 따른 노래들을 정리한다.

구현, 설계

  • 장르별로 노래가 몇 번 재생 되었는지 기록한다.
  • 해당 장르에 속한 노래의 재생 시간, 고유 번호를 기록한다.

  • 조건에 맞춰서 정렬해 나가며 답을 낸다.

  • map은 오름차순 정렬이다. 이것을 음수로 취해 내림차순 정렬로 유도할 수 있다.
  • 첫 번째 풀이에서는 cmp 를 따로 만들어서 정렬했다.
  • 두 번째 풀이에서는 음수 를 이용해 내림차순을 유도해서 정렬했다.

주의할 점

  • 장르에 속한 곡이 하나인 경우를 고려한다.

코드

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
92
93
94
95
96
97
98
99
100
101
102
103

#if 00
#include<bits/stdc++.h>
using namespace std;

struct music {
    int play_cnt;
    int music_number;
};

bool cmp(const music &a, const music &b) {
    if (a.play_cnt == b.play_cnt) return a.music_number < b.music_number;
    else return a.play_cnt > b.play_cnt;
}



map<string, pair<int, vector<music> > > musics;

vector<int> answer;
vector<int> solution(vector<string> genres, vector<int> plays) {
    int len = plays.size();

    for (int i = 0; i < len; ++i) {
        string type = genres[i];
        int type_cnt = plays[i];
        int uniq_num = i;

        musics[type].first += type_cnt;
        musics[type].second.push_back({ type_cnt, uniq_num });
    }

    map<int, vector<music> > tmp;

    for (auto it = musics.begin(); it != musics.end(); ++it) {
        tmp[it->second.first] = it->second.second;
    }
    
    for (auto it = tmp.rbegin(); it != tmp.rend(); ++it) {
        vector<music> &vec = (it->second);
        sort(vec.begin(), vec.end(), cmp);

        for (int i = 0; i < vec.size() && i < 2; ++i) {
            answer.push_back(vec[i].music_number);
        }
    }

    return answer;
}

#else

#include<bits/stdc++.h>
#define pp pair<int, int>

using namespace std;

unordered_map<string, pair<int, vector<pp> > > musics;

vector<int> answer;
vector<int> solution(vector<string> genres, vector<int> plays) {
    int len = plays.size();

    for (int i = 0; i < len; ++i) {
        string type = genres[i];
        int type_cnt = -plays[i];
        int uniq_num = i;

        musics[type].first += type_cnt;
        musics[type].second.push_back({ type_cnt, uniq_num });
    }

    map<int, vector<pp> > tmp;

    for (auto it = musics.begin(); it != musics.end(); ++it) {
        tmp[it->second.first] = it->second.second;
    }

    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        vector<pp>& vec = it->second;
        sort(vec.begin(), vec.end());

        for (int i = 0; i < vec.size() && i < 2; ++i) {
            answer.push_back(vec[i].second);
        }
    }
    return answer;
}

#endif

int main() {

    vector<string> ge = { "classic", "pop", "classic", "classic", "pop", "lock" };
    vector<int> p = { 500, 600, 150, 800, 2500, 100 };
    vector<int> ans = solution(ge, p);

    for (auto it : ans) {
        cout << it << " ";
    }

    return 0;
}

Java 코드

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
import java.util.*;

class Solution {

    List<Integer> answer = new ArrayList<>();
    Map<String, Integer> typeMap = new HashMap<>();
    Map<String, List<Pair>> playMap = new HashMap<>();

    public List<Integer> solution(String[] genres, int[] plays) {
        for (int i = 0; i < genres.length; ++i) {
            String type = genres[i];
            int playIndex = i;
            int playCount = plays[i];

            typeMap.put(type, typeMap.getOrDefault(type, 0) + playCount);

            List<Pair> list = playMap.getOrDefault(type, new ArrayList<>());
            list.add(new Pair(playCount, playIndex));
            playMap.put(type, list);
        }

        Map<Integer, String> orderedTypes = new TreeMap<>();
        for (String type : typeMap.keySet()) {
            orderedTypes.put(-typeMap.get(type), type);
        }

        for (Integer playCount : orderedTypes.keySet()) {
            String type = orderedTypes.get(playCount);
            List<Pair> list = playMap.get(type);
            Collections.sort(list);

            for (int i = 0; i < list.size() && i < 2; ++i) {
                answer.add(list.get(i).number);
            }
        }
        return answer;
    }
}

class Pair implements Comparable<Pair> {
    int playCount;
    int number;

    public Pair(final int playCount, final int number) {
        this.playCount = playCount;
        this.number = number;
    }

    @Override
    public int compareTo(final Pair o) {
        if (this.playCount == o.playCount) {
            return Integer.compare(this.number, o.number);
        } else {
            return -Integer.compare(this.playCount, o.playCount);
        }
    }
}

피드백

cpp

  • map은 key값을 기준으로 정렬 된다는 것을 또 깜박 했다.
  • 항상 양수만 나온다는 조건에서는 음수를 이용하여 의도적으로 내림차순을 유도할 수 있다는 것을 알게 되었다.

java

  • java의 경우 map을 다루는것이 굉장히 불편하다. 디폴트값이 있는지 일일히 확인해줘야한다. getOrDefault 를 이용해 수고를 줄일 수 있다.
  • 싱글톤 List를 쓰는걸 지양하자.