폰켓몬

문제

문제에서 n값은 10000 으로 시간복잡도 $O(n^2)$ 이하에 풀이를 작성하면 됐다.

풀이

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> nums)
{
    int max = nums.size()/2;
    int answer = 0;
    unordered_map<int,int> map;
    for(int elem : nums)
    {
        if(map.end() == map.find(elem))
        {
            map.insert(make_pair(elem,1));
        }
        else
        {
            map[elem]++;
        }
    }
    
    answer = map.size();
    if(answer > max) answer = max;
    return answer;
}

해시테이블을 이용하여 문제를 풀었다. 이 앞전에 문제를 풀면서 배웠던 unorderd_map을 사용해봤다. 먼저 해쉬테이블에 nums를 다 추가를 해주었다. 이때 중복된 키값을 가지고 있는 경우에는 value에 값만 ++ 해주고 추가를 해주지는 않는다.

그리고 map의 size를 확인하여 답을 도출하였다.