간단한 Map 구현 하기

https://leetcode.com/problems/design-hashmap/

오늘의 문제는 내장 해시 테이블 라이브러리 없이 해시맵을 직접 구현하는 문제였다.

문제는 다음과 같은 기능을 가진 MyHashMap 클래스를 구현하는 것이다.

• MyHashMap() - 빈 맵으로 객체를 초기화
• put(key, value) - 키-값 쌍을 삽입하거나 기존 키의 값을 업데이트
• get(key) - 특정 키에 매핑된 값을 반환하거나 키가 없으면 -1 반환
• remove(key) - 키와 해당 값을 제거

키 값이 문자열인 줄 알았으나 정수 범위로 제한되어 있어서 구현이 매우 간단한 문제이다.

시간 복잡도를 낮추는 방향으로 간단하게 구현해 보았다.

간단한 배열 기반 구현

배열을 직접 사용하는 방식이다. 문제의 제약 조건에 따라 키와 값이 0에서 10^6 사이라는 점을 활용했다.

class MyHashMap:
    def __init__(self):
        self.hashMap = [-1] * 1000001 # 입력 제한 길이: 1000000

    def put(self, key: int, value: int) -> None:
        self.hashMap[key] = value

    def get(self, key: int) -> int:
        return self.hashMap[key]

    def remove(self, key: int) -> None:
        self.put(key, -1)

이 접근법의 특징

• 시간 복잡도: 모든 연산이 O(1) - 인덱스 접근은 상수 시간
• 공간 복잡도: O(10^6) - 입력 범위에 맞는 고정 크기 배열
• 장점: 구현이 단순하고 모든 연산이 매우 빠르다
• 단점: 고정 크기 배열을 미리 만듦으로서 메모리 사용량이 많다