LeetCode August2.Design HashSet

1. 문제(원본)

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

To be specific, your design should include these functions:

• add(value): Insert a value into the HashSet. 
• contains(value) : Return whether the value exists in the HashSet or not.
• remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

MyHashSet hashSet = new MyHashSet();

hashSet.add(1);        

hashSet.add(2);        

hashSet.contains(1);    // returns true

hashSet.contains(3);    // returns false (not found)

hashSet.add(2);          

hashSet.contains(2);    // returns true

hashSet.remove(2);          

hashSet.contains(2);    // returns false (already removed)

Note:

• All 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 HashSet library.

2. 문제

정수형 해쉬 테이블을 만들어라

3. 나의 답

class MyHashSet {

 

    var max = 100

    var array: [Int] = []

    

    /** Initialize your data structure here. */

    init() {

        array = Array(repeating: -1, count: max + 1)

    }

    

    func add(_ key: Int) {

        if key > max {

            let add = Array(repeating: -1, count: key - max)

            array.append(contentsOf: add)

            max = key

        }

        array[key] = key

        print(array)

    }

    

    func remove(_ key: Int) {

        if key > max { return }

        array[key] = -1

    }

    

    /** Returns true if this set contains the specified element */

    func contains(_ key: Int) -> Bool {

        if key > max { return false }

        return (array[key] != -1)

    }

}

4. 다른 유저의 답

#1

미공개

5. 마무리

이번 문제를 풀면서 드는 생각은 예전에도 비슷한 문제를 풀었던 기억이 있어서 복습할 겸 풀었는데 풀고 나니 몸에 익은 느낌이 들어 한 단계 성장한 기분을 느꼈다. 예전에는 진짜 많이 고군분투하다가 전체적인 크기를 지정해서 만들었었는데 그때 다른 유저의 답으로 학습한 메모리에 부담을 덜어주는 방법으로 진행하였다.

적당히 임의의 크기를 지정한 배열을 만들어주고 그 크기 이상의 값이 들어온다면 동적으로 배열의 크기를 늘려나가는 방법이다. 뭔가 자신감을 얻은 것 같다.