[neetcode.io roadmap project] - Arrays & Hashing
아래는 leetcode 347. Top K Frequent Elements를 푼 흐름입니다.
0. 문제의 이해
문제의 입력은 nums 배열과 정수 k입니다.
이때, nums 배열에서 원소들(~)이 나온 횟수가 있을 것입니다.
ex) nums = [10,10,10,100,100] 이면, 10 ->3회, 100 -> 2회.
이때 가장 많이 나온 배열의 원소들을 내림차순으로 K개 출력하는 것이 문제의 요구사항입니다.
(이때, 입력의 정답은 unique하므로 중복된 횟수를 처리할 필요는 없습니다.)
1. Runtime 29ms // Memory 14 MB 풀이
class Solution {
public:
static bool comp(pair<int, int>& a, pair<int, int>& b){
if(a.second > b.second) return true;
return false;
} // second값(나온 횟수) 기준으로 내림차순 정렬하기 위한 comp함수
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int, int> store; //[Key: 원소, Value : 나온 횟수] 인 map
vector<int> result;
for(int i = 0; i < nums.size(); ++i){
if(store.find(nums[i]) != store.end()){
store.find(nums[i])->second += 1;
} else {
store.insert({nums[i], 1});
}
}
vector<pair<int, int>> mp(store.begin(), store.end()); //map정렬을 위한 vector
sort(mp.begin(), mp.end(), comp); //value기준 내림 차순 정렬
for(int i = 0; i < k; ++i){
result.push_back(mp[i].first);
}
return result;
}
};위 코드의 핵심은 Key-Value를 저장할 수 있는 std::map을 활용해 nums배열의 원소를 Key, 각 원소가 나온 횟수를 Value로 저장한 것입니다.
이후 map을 vector로 변환한 수 내림차순으로 정렬한 수 K개 만큼 result vector에 넣은 후 반환하였습니다.
Memory👉 map변수의 메모리, map변수 정렬을 위한 vector변수의 메모리를 사용해 메모리를 많이 차지하니다.
Time👉 nums vector을 전부 순회하여 map을 수정해주는 O(n), map을 새로운 vector에 복사해주는 O(n), vector 변수를 정렬하는 O(n log n)로 전체 시간복잡도는 O(n log n + 2n) = O(n log n)입니다.
2. Runtime 23ms // Memory 15.5 MB 풀이
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int, int> store; //[Key: 원소, Value : 나온 횟수] 인 map
vector<int> result;
for(int i = 0; i < nums.size(); ++i){
if(store.find(nums[i]) != store.end()){
store.find(nums[i])->second += 1;
} else {
store.insert({nums[i], 1});
}
} //nums를 순회하며 store 업데이트
vector<vector<int>> count(nums.size()+1); //Bucket sort를 위한 count vector
//각 원소의 최대 중복 개수는 nums배열의 길이와 같으므로 nums.size()+1 길이로 생성함(이하 설명)
for(auto val : store){ //각 '원소가 나온 횟수'의 인덱스에 '원소'를 vector뒤에 넣어줌
count[val.second].emplace_back(val.first); //공간 효율을 위해 emplace_back()사용
}
for(int i = count.size()-1; i >= 0; --i){ //result vector의 크기가 k가 될 때 까지 삽입
for(auto val : count[i]){
result.emplace_back(val);
}
if(result.size() == k) break;
}
return result;
}
};다음은 공간을 희생하여 시간을 줄인 방법입니다.
1번 코드와 다른 점은 map을 vector에 넣어서 정렬한 것이 아닌, 새로운 count vector을 만들었습니다.
count vector의 index는 nums에서 각 원소가 나온 횟수를 의미합니다.
count vector의 각 index에는 nums에서 index 횟수만큼 나온 원소가 vector로 저장됩니다.
예를 들어 nums=[1,2,2,3,3]이라면 1이 1번, 2가 2번, 3이 2번 나왔으므로
count배열은 count = [[], [1], [2, 3], [], [], []]이 되도록 한다는 것입니다. (1이 index 1에, 2와 3이 index 2에.)
이러한 방식이라면 count배열을 역으로 순회하며 result vector에 만나는 vector원소들의 원소들을 추가하기만 하면 되는 것입니다.
이때 답은 유일하므로 count vector의 원소 vector을 만날 때마다 원소 vector의 모든 원소들을 추가해줘도 됩니다.
3. Runtime 7ms // Memory 15.4 MB 풀이
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> store; //map대신 unordered_map사용
vector<int> result;
for(auto i : nums){ //store변수를 업데이트 하는 방식 수정.
++store[i];
}
vector<vector<int>> count(nums.size()+1);
for(auto val : store){
count[val.second].emplace_back(val.first);
}
for(int i = count.size()-1; i >= 0; --i){
for(auto val : count[i]){
result.emplace_back(val);
}
if(result.size() == k) break;
}
return result;
}
};마지막은 std::map대신 std::unordered_map을 사용하여 시간을 비약적으로 줄인 코드입니다.
추가로 store을 업데이트 하는 방식도 수정했습니다.
검색을 해본 결과, Key값으로 Value를 찾을 때 map은 red-black tree구조를 사용하여 O(log n)이 걸리지만 unordered_map은 Hash Table을 사용하기 때문에 O(1)이 걸립니다.
추가 std containers에 대한 포스트는 링크 참조
제 코드에서는 store변수를 업데이트 할 때 가장 시간이 많이 줄어들었다고 추정할 수 있습니다.
4. Conclusion
위 문제를 통해서 배울 수 있었던 점은
- Bucket Sort에서 Bucket을 사용하는 방식(링크)처럼 count배열을 활용해 원소들을 새롭게 정렬하는 방식
- map과 unordered_map의 차이와 그 이유
- Hash map이라고 하면 일반적으로 unordered_map이라는 점
입니다.
