아래의 문제에 대하여 C++ 의 해쉬에 해당하는 unordered map 과 array 로 구현했을 때, 속도 비교를 하고자 합니다
최빈값 문제는 다음과 같습니다
Array 기반으로 해결하는 방법의 코드입니다
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> array) {
int array_list[1000] = {0,};
int max = 0;
int out = -1;
for (int i = 0; i < array.size(); i++) {
array_list[array[i]] += 1;
if (array_list[array[i]] > max) {
max = array_list[array[i]];
out = array[i];
} else if (array_list[array[i]] == max) {
out = -1;
}
}
return out;
}
Hash 기반으로 해결하는 다른 분의 코드입니다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<int> array) {
int answer = 0;
int maxV = 0;
unordered_map<int,int> um;
for(const auto v : array)
{
um[v]++;
}
for(const auto& v : um)
{
if(v.second > maxV)
{
maxV = v.second;
answer = v.first;
}
else if(v.second == maxV)
{
answer = -1;
}
}
return answer;
}
실행결과: 특정 데이터에서 Hash 기반 구현이 Array 기반 구현보다 느린 것을 확인할 수 있습니다
#include <iostream>
#include <vector>
using namespace std;
void makeVector(vector<int>& Mat, int row, int col);
int main() {
int N, M, K;
vector<int> A, B, AB;
cin >> N >> M;
A.reserve(sizeof(int) * N * M);
makeVector(A, N, M);
cin >> M >> K;
B.reserve(sizeof(int) * M * K);
makeVector(B, M, K);
AB.reserve(sizeof(int) * N * K);
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
int ele = 0;
for (int k = 0; k < M; k++) {
ele += A[i * M + k] * B[j + k * K];
}
cout << ele << ' ';
}
cout << endl;
}
return 0;
}
void makeVector(vector<int>& Mat, int row, int col) {
int tmp;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
cin >> tmp;
Mat.push_back(tmp);
}
}
}
