[Leetcode 아주 상세한 문제풀이] 706. Design HashMap - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 706번 문제 Design HashMap 다.

우선 문제를 살펴보자.

 

리트코드 706번 문제 Design HashMap 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:
Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]
 

Constraints:
0 <= key, value <= 106
At most 104 calls will be made to put, get, and remove.

 

 

문제 설명

문제를 간략히 살펴보자. 이번 문제는 빌트인 해쉬 테이블 라이브러리를 이용하지 않고 hashmap을 구현해 보는 것이다. 

우선 hashmap 에 대해 알아보자.

해시맵(Hashmap) 에 대해

해시맵(HashMap)은 키(Key)와 값(Value)을 연결하는 자료구조로, 연관 배열 또는 사전(Dictionary)이라고도 한다. 해시맵은 데이터를 저장하고 검색하는 데 매우 효율적인 방법이다. 해시맵에 대한 주요 특징은 다음과 같다.

1) 키-값 쌍: 해시맵은 데이터를 키와 값의 쌍으로 저장한다. 각 키는 고유하며 해당 키를 사용하여 값을 빠르게 검색할 수 있다.

2) 해싱 함수: 해시맵의 핵심은 해싱 함수다. 이 함수는 키를 받아 해시 코드(인덱스)를 계산하며, 이 해시 코드는 키-값 쌍이 테이블에 저장될 위치를 결정한다. 이 함수는 가능한 한 테이블 전체에 걸쳐 키를 균일하게 분포시켜야 한다.

3) 충돌 처리: 서로 다른 키가 같은 해시 코드를 가질 때 충돌이 발생한다. 충돌을 처리하는 방법으로는 체이닝(Chaining), 오픈 어드레싱 (Open Addressing) 등이 있다.

4) 시간 복잡도: 최적의 경우, 각 조회, 삽입 또는 삭제 작업의 평균 시간 복잡도는 O(1)이다. 즉, 상수 시간이며 테이블의 항목 수에 의존하지 않는다. 그러나 최악의 경우(예: 모든 키가 충돌할 때) 이러한 작업은 O(n)으로 느려질 수 있다.

 

 

문제 접근법

이 문제를 해결하기 위해서는 우리는 파이썬의 배열 (list array)을 이용할 것이다.

문제의 요건에 따라 key와 value 값은 정수이고 호출은 제한적이다.

따라서 우리는 충분히 큰 배열을 만들어 모든 key 값들을 바로 저장하는 방식을 사용할 것이다.

우리는 hashmap 구현을 위해 1,000,001의 크기를 가지는 배열을 이용할 것이다.

이때 각 index는 각 key값에 직접적으로 연관된다.

Put method는 value 값을 그에 해당하는 index에 곧바로 넣는 것이다.

Get method는 key에 해당하는 index의 value 값을 리턴하는 것이다.

이때 만약 해당하는 value 값이 없다면 -1을 리턴한다.

Remove method는 key에 해당하는 값을 none으로 바꾼다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

Hashmap 구현을 위한 class를 선언해준다. (line 1)

우선 hashmap 데이터 구조 초기화를 해준다.

Hashmap의 사이즈는 1,000,001로 초기화 해주고 (line 6) map size는 이와 동일하게 해준다. (line 7)

먼저 put method를 구현하기 위한 함수를 정의해 준다. (line 9)

이때 key에 해당하는 index에 해당 value를 넣어준다. (line 13)

그 다음으로 get method를 구현하기 위한 함수를 정의해 준다. (line 15)

이때 key에 해당하는 index를 이용해 map에서 해당 value 값을 가져온다. (line 19)

만약 value 값이 존재하지 않는 경우 -1을 리턴해준다. (line 20)

마지막으로 remove method를 구현하기 위한 함수를 정의해 준다. (line 22)

이때 key에 해당하는 index 값을 이용해 map에서 해당 value 값을 none으로 바꾼다. (line 26)

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.longest = 0
 
        def dfs(node):
            if not node:
                return 0
 
            left_length = dfs(node.left)
            right_length = dfs(node.right)
 
            left_path = right_path = 0
 
            if node.left and node.left.val == node.val:
                left_path = left_length + 1
 
            if node.right and node.right.val == node.val:
                right_path = right_length + 1
 
            # Update the longest path found so far
            self.longest = max(self.longest, left_path + right_path)
 
            # Return the length of the longest path ending at this node
            return max(left_path, right_path)
 
        dfs(root)
        return self.longest
 
# Example usage
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(1)
root.right.right = TreeNode(5)
 
sol = Solution()
print(sol.longestUnivaluePath(root))  # Output: 2
 

 

 

706. Design HashMap