프로그래머스_폰켓몬

코딩테스트 연습 > 해시 > 폰켓몬

해시 카테고리임에도 벡터를 소팅해서 풀었음...
해시도 정확히 알아둬야 쓸 수 있으니 조금씩 정리해두려고 함

기존 풀이

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 1;
    int idx = 0;
    int nums_size = nums.size();
    sort(nums.begin(), nums.end());
    while (answer < nums_size * 0.5) {
        if (idx + 1 < nums_size) {
            if (nums[idx] != nums[idx + 1]) {
                ++answer;
            }
            ++idx;
        }
        else break;
    }
    return answer;
}

수정한 풀이

#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<int> nums)
{
    unordered_map<int, int> poke;
    for (auto num: nums) {
        poke[num] += 1;
    }
    return min(poke.size(), nums.size() / 2);
}

unordered_map

• 해시 테이블로 구현된 unordered_map은 중복된 key 값은 포함하지 않고 버려버리기 때문에 이 문제처럼 복잡하지 않은 중복값을 정리하는 데 효과적임.
• 탐색 시간복잡도는 O(1)임. O(log n)인 map에 비해 성능이 우월함. 전반적으로 map의 상위호환임.
• 그러나 key가 유사한 데이터가 많은 경우 잦은 해시 충돌로 성능이 저하됨.
• index로 접근하지 못함. iterator로 접근해야 함.

참고: 링크