99클럽 코테스터디 6기 09일차 TIL (LeetCode 706)

문제접근

문제 : LeetCode 706. Design HashMap
(https://leetcode.com/problems/design-hashmap/description/)

해시맵을 이용하여 <key, value>를 put, get, remove하는 함수를 구현하라.

1) 해시맵에 대한 이해
C++ map, unordered_map 정리

제출코드

#include <vector>
#define SIZE 10000
class MyHashMap {
private:
    vector<vector<pair<int, int>>> hv;
    int hashKey;

public:
    MyHashMap() : hv(SIZE) {
        
    }
    
    void put(int key, int value) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) {
            hv[hashKey].push_back({key, value});
            return;
        }
        for(auto& k : hv[hashKey]) {
            if (k.first == key) {
                k.second = value;
                return;
            }
        }
        hv[hashKey].push_back({key, value});
        return;
    }
    
    int get(int key) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) return -1;
        for (auto& k : hv[hashKey]) {
            if (k.first == key) return k.second;
        }
        return -1;
    }
    
    void remove(int key) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) return;
        for (auto it = hv[hashKey].begin(); it != hv[hashKey].end(); it++) {
           if (it->first == key) {
            hv[hashKey].erase(it);
            return;
           }
        }
        return;
        
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

문제 해결

1. 해시맵 이해
   처음에는 해시맵에 대한 이해 없이 <key, value> 쌍을 단순히 벡터에 저장하고 선형 탐색으로 구현하였다. 기능 구현에는 성공했지만 해시맵의 핵심인 해시 함수를 활용하지 못했기 때문에, 이후 해시 함수를 적용한 방식으로 문제를 다시 해결하였다.
2. 해시 함수 및 충돌 관리
   충돌 해결 방법으로는 이중 해시보다는 구현이 간단한 체이닝 방식을 선택하였고, 2차원 벡터를 이용해 구조를 설계하였다. 연결 리스트와 벡터 중 고민한 끝에 탐색 속도가 더 빠른 벡터를 사용해 구현하였다.

---

오늘의 회고

함수 기능뿐 아니라 요구하는 구조에 맞게 구현하도록 하자.