1. 문제(원본)
Design a HashMap without using any built-in hash table libraries.
To be specific, your design should include these functions:
- put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
- get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
- remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.
Example:
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)
Note:
- All keys and values will be in the range of [0, 1000000].
- The number of operations will be in the range of [1, 10000].
- Please do not use the built-in HashMap library.
2. 문제
주어진 조건을 가진 HashMap을 디자인하라
class MyHashMap {
/** Initialize your data structure here. */
init() {
}
/** value will always be non-negative. */
func put(_ key: Int, _ value: Int) {
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func get(_ key: Int) -> Int {
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func remove(_ key: Int) {
}
}
3. 나의 답
class MyHashMap {
// All keys and values will be in the range of [0, 1000000].
// The number of operations will be in the range of [1, 10000].
var array: [Int]
/** Initialize your data structure here. */
init() {
self.array = Array(repeating: -1, count: 1000001)
}
/** value will always be non-negative. */
func put(_ key: Int, _ value: Int) {
self.array[key] = value
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func get(_ key: Int) -> Int {
return self.array[key]
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func remove(_ key: Int) {
self.array[key] = -1
}
}
4. 다른 유저의 답
#1
class MyHashMap {
var array = [Int]()
/** Initialize your data structure here. */
init() {
}
/** value will always be non-negative. */
func put(_ key: Int, _ value: Int) {
if array.count <= key {
array += Array(repeating: -1, count: key - array.count + 1)
}
array[key] = value
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func get(_ key: Int) -> Int {
guard key < array.count else { return -1 }
return array[key]
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func remove(_ key: Int) {
guard key < array.count else { return }
array[key] = -1
}
}
5. 마무리
처음에 문제를 잘못 이해해서 그냥 단순히 디자인만 하면 되는 줄 알고 이거 그냥 Dictionary 쓰면 되는 거 아닌가? 했는데 다시 한번 읽어보니 그런 문제를 낼 리가 없다는 것을 알고 새로 디자인을 해보았다. 디자인 자체는 금방 끝났는데 역시나 Limit 메모리의 한계의 벽에 부딪혀 어떻게 해결해 나가야 하나 진짜 여러 방면으로 고민을 많이 했다. 아래가 이전의 나의 답변이다.
class MyHashMap {
struct HashMap {
var key: Int
var value: Int
}
var array: [HashMap]
/** Initialize your data structure here. */
init() {
self.array = []
}
/** value will always be non-negative. */
func put(_ key: Int, _ value: Int) {
let data = HashMap(key: key, value: value)
for (index, element) in self.array.enumerated() where element.key == key {
self.array[index] = data
return
}
self.array.append(data)
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func get(_ key: Int) -> Int {
for element in self.array where element.key == key {
return element.value
}
return -1
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func remove(_ key: Int) {
for (index, element) in self.array.enumerated() where element.key == key {
self.array.remove(at: index)
return
}
}
}
막상 디자인을 끝내고도 괜찮네 그럴싸하다 라고 생각을 했는데 결과는 타임 오버.. 역시나 전체적인 처리에 for문을 사용하고 있었기 때문에 배열의 크기가 상당해지면 처리 속도가 엄청 느려지는 것을 알 수 있었다.
그래서 해결하겠다고 한 처리가 밑의 조건이었는데
- All keys and values will be in the range of [0, 1000000].
애초에 배열을 해당 키의 수만큼 만들고 시작하면 처음 초기화 시에는 조금 시간이 걸리더라도 후의 처리에서는 시간이 별로 필요하지 않을 것이라고 생각했다. 나의 예상은 적중했고 몇몇 유저들도 이와 같이 푼 것을 볼 수 있었다. 하지만! 이건 어디까지나 키의 범위를 지정해 주었을 때이고 개발자라면 항상 동적인 생각 예외적인 생각을 해야 한다고 생각한다. 문제는 풀었지만 프로그램 적으로는 오답이나 다름없다.
그 와중에 보인 것은 위의 다른 유저의 해답... 배열의 크기에 맞추어 유연하게 변화시키는 답변이 나를 다시 한번 공부시키게 되었다.
이번 문제를 통해 알게 된 것
- 내가 생각하는 이상적인 답변은 구현할 수 있다. 좀 더 생각하자
- Dictionary의 대단함
Dictionary가 더 빠르고 안정적이었다. (감사감사)
'알고리즘 > 고군분투' 카테고리의 다른 글
| LeetCode August3.Valid Palindrome (0) | 2020.08.06 |
|---|---|
| LeetCode206. Reverse Linked List (0) | 2020.04.14 |
| LeetCode888. Fair Candy Swap (0) | 2020.04.12 |