LeetCode 706. Design HashMap

파이썬 알고리즘 인터뷰 문제 28번(리트코드 706번) Design HashMap
https://leetcode.com/problems/design-hashmap/

나의 풀이

class MyHashMap:

    def __init__(self):
        self.keys = []
        self.values = []

    def put(self, key: int, value: int) -> None:
        update = False
        for i, x in enumerate(self.keys):
            if x == key:
                self.values[i] = value
                update = True
                break
        if not update:
            self.keys.append(key)
            self.values.append(value)

    def get(self, key: int) -> int:
        for i, x in enumerate(self.keys):
            if x == key:
                return self.values[i]
        return -1

    def remove(self, key: int) -> None:
        for i, x in enumerate(self.keys):
            if x == key:
                del self.keys[i]
                del self.values[i]

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

• 대충 주어진 메서드만 구현되면 된다고 생각하고 이렇게 풀었다.
• 하지만 hash를 사용하지 않았으므로 잘못된 풀이임.

다른 풀이(책 풀이)

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        index = key % self.size

        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return
        
        p = self.table[index]
        while p:
            if p.key == key:
                p.value = value
                return
            if p.next is None:
                break
            p = p.next
        p.next = ListNode(key, value)
        

    def get(self, key: int) -> int:
        index = key % self.size

        if self.table[index].value is None:
            return -1
        
        p = self.table[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1 #이게 왜 필요하지

    def remove(self, key: int) -> None:
        index = key % self.size

        if self.table[index].value is None:
            return 
        
        p = self.table[index]
        if p.key == key:
            if p.next is None:
                self.table[index] = ListNode()
            else:
                self.table[index] = p.next
            return
        
        prev = p

        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.next

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

• hash table로 defaultdict을 사용하고 Linked List를 이용한chainging방식으로 구현하였음.
• hash를 바탕으로 만들어진 defaultdict을 쓰는 것은 편법이라 생각함.

다른 풀이(책 풀이 개선)

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.table = [None]*self.size
        #self.table = [[]]*self.size 이렇게 했다가 얕은 복사라서 오답
        

    def put(self, key: int, value: int) -> None:
        index = key % self.size
        if not self.table[index]:
            self.table[index] = ListNode(key, value)
            return
        prev = self.table[index]
        if prev.key == key:
            prev.value = value
            return
        while prev:
            if prev.key == key:
                prev.value = value
                return
            if not prev.next:
                break
            prev = prev.next
        prev.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.size
        if not self.table[index]:
            return -1
        prev = self.table[index]
        while prev:
            if prev.key == key:
                return prev.value
            prev = prev.next
        return -1
        

    def remove(self, key: int) -> None:
        index = key % self.size
        if not self.table[index]:
            return
        prev = self.table[index]
        if prev.key == key:
            if prev.next:
                self.table[index] = prev.next
            else:
                self.table[index] = None
            return
        while prev.next:
            if prev.next.key == key:
                break
            prev = prev.next
        if prev.next:
            prev.next = prev.next.next

        

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

• hash table로 defaultdict대신 list를 이용하였음.

오답, 배운 점

• 마지막 풀이에서 처음 'hash table 만들 때 [[]]*size로 만들었다가 오답나오고 [None]*size로 바꾸었다.
• 오답이 나온 이유는 얕은 복사(Shallow copy) 때문으로 자세한 내용은 아래 글을 참조하자.

파이썬의 얕은 복사에 대한 글
https://velog.io/@coding_study/파이썬에서-연산자와-얕은-복사Shallow-Copy