알고리즘 기법
- 정렬
자료구조
- hash table
설명
문제가 요구하는 바는 다음과 같다.
1. 각 장르마다 총 몇 번 재생되었는지 저장하고 이를 바탕으로 장르를 정렬한다.
2. 장르 별로 노래를 정렬한다.
2-1. 이 때 각 노래의 재생 횟수가 많은 것이 앞에 오도록 정렬한다.
2-2. 재생 횟수가 같다면 노래의 번호가 작은 것이 앞에 오도록 정렬한다.
3. 1에서 구한 장르 순서대로 장르를 선택하여, 2에서 구한 각 장르 별 노래들에서 2개 혹은 1개씩 뽑고,
이를 answer 배열에 저장한다.1번 요구사항
hash table을 사용한다.
그 이유는 genres 배열이 뒤죽박죽 섞여 있기 때문이다.
(genre를 통해 노래 횟수에 접근할 때 이론적으로 O(1)을 보장하여 해당 상황에서 가장 빠른 자료구조다.)
이 때, hash table의 key는 string(장르 이름)이고 value는 integer(재생 횟수)다.
각 장르마다 총 재생횟수를 저장했다면 이를 바탕으로 genre들을 정렬해 줘야 한다.
(정렬된 genre 배열을 통해 답을 구할 때 어떤 장르에서 먼저 노래를 선택할지 알 수 있다.)
2번 요구사항
마찬가지로 hash table을 사용한다.
그 이유는 1번 요구사항의 마지막에 정렬한 genre 배열을 통해 노래들에 접근해야 하는데,
{key, value}가 {string(장르 이름), 배열({재생횟수, 노래번호})}인 hash table은 접근할 때 O(1)의 시간을 보장하기 때문이다.
위와 같은 {key, value} 구조의 hash table을 만든 뒤, 각 장르마다 배열을 2번 요구사항의 세부사항에 맞춰서 정렬해줘야 한다.
(이를 통해 장르 내에서 어떤 노래를 뽑아야 하는지 알 수 있다.)
3번 요구사항
1번, 2번의 결과를 이용하여 답을 구한다.
소스코드
cpp
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
bool cmp(vector<int> &a, vector<int> &b) {
if (a[0] > b[0])
return true;
if (a[0] == b[0] && a[1] < b[1])
return true;
return false;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
// 장르마다 몇 번 재생되었는지 알아야 함.
// -> hash로 장르 별로 재생 횟수 저장
// -> 위에서 저장한 것을 바탕으로 장르 정렬
// 장르 내에서 많이 재생된 녀석 순으로 정렬
// 장르 내에서 재생된 횟수가 같으면 id 낮은 순으로 정렬
// -> 장르를 key로하고 {{재생횟수, id}, ...}벡터를 value로 하는 해시 -> 장르별로 벡터를 정렬
/* 장르 순서 정하기 */
unordered_map<string, int> genre_play_cnt_hash;
vector<string> genre_order;
int len = (int)plays.size();
for (int i = 0; i < len; i++) {
if (genre_play_cnt_hash.find(genres[i]) == genre_play_cnt_hash.end())
genre_play_cnt_hash.insert({genres[i], plays[i]});
else
genre_play_cnt_hash[genres[i]] += plays[i];
}
unordered_map<string,int>::iterator it = genre_play_cnt_hash.begin();
unordered_map<string,int>::iterator it_end = genre_play_cnt_hash.end();
for (; it != it_end; it++)
genre_order.push_back(it->first);
sort(genre_order.begin(), genre_order.end(), [&genre_play_cnt_hash](string &a, string &b)->bool{
if (genre_play_cnt_hash[a] > genre_play_cnt_hash[b])
return true;
return false;
});
/* 장르별 노래 순서 정하기 */
unordered_map<string, vector<vector<int>>> play_id_each_genre;
for (int i = 0; i < len; i++) {
if (play_id_each_genre.find(genres[i]) == play_id_each_genre.end())
play_id_each_genre[genres[i]] = {{plays[i], i}};
else
play_id_each_genre[genres[i]].push_back({plays[i],i});
}
unordered_map<string,vector<vector<int>>>::iterator it2 = play_id_each_genre.begin();
unordered_map<string,vector<vector<int>>>::iterator it2_end = play_id_each_genre.end();
for (; it2 != it2_end; it2++)
sort(it2->second.begin(), it2->second.end(), cmp);
/* 답 구하기 */
for (string &genre : genre_order) {
vector<vector<int>> &temp_vec = play_id_each_genre[genre];
answer.push_back(temp_vec[0][1]);
if (temp_vec.size() >= 2)
answer.push_back(temp_vec[1][1]);
}
return answer;
}참고
cpp에서 mapping을 위한 STL 자료구조는 map과 unordered_map 2가지가 있다.
1. map은 균형 이진 트리를 이용하며 순서대로 자료를 저장한다.
삽입 삭제 접근이 O(log(n))을 만족한다.
2. unordered_map은 hash table 기반의 자료구조이며 당연히 순서는 상관없다.
삽입 삭제 접근이 O(1)을 만족한다.언뜻 unordered_map이 훨씬 좋아 보이지만 자료가 많아진다면 hash table에서 bucket 충돌이 발생할 수 있어 상황에 따라 unordered_map을 선택할지 map을 선택할지 결정해줘야 한다.
unordered_map 사용법
- key가 있는지 확인하기
- .find(key) -> return iterator
- (key가 있으면 해당 반복자를, 없으면 .end()의 결과를 반환한다.)
- 접근 삽입/수정
- hash_table[key];
- hash_table[key] = value;
- 삭제
- .erase(iterator) or .erase(key)
