[C++] 해쉬(unordered map) vs 배열 속도 비교 - 프로그래머스 최빈값 구하기

아래의 문제에 대하여 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 기반 구현보다 느린 것을 확인할 수 있습니다