[leetcode - 380. Insert Delete GetRandom O(1)] java

문제 설명

1. 랜덤셋? 을 만들어라

2. insert -> 값이 있으면 false, 없으면 값을 저장하고 true

3. remove -> 값이 없으면 false, 있으면 값을 제거하고 true

4. getRandom -> 지금까지 저장된 값들 중 랜덤으로 하나 가져와서 보여줌

풀이 과정 

1. 알고..리즘? 맞나 이거?

2. 그냥 위의 내용을 구현하면 되는데, O(1) 을 위해서는 아무래도 자료구조에 대해서 알고 있어야 할 것 같다.

3. 사실 나는 그냥 간단하게 했는데 더 성능에 좋은 방법이 있을 듯 싶다.

4. ArrayList 

    - getRandom을 위해 사용할 수밖에 없었다.

    - contains의 경우 O(n) 이라서 사용하지 않음

    - remove는 어쩔 수 없이 사용했다. 다른 방식을 쓰려고 해도 random 출력을 위해서는 이게 필요하다.

    - get은 O(1)

5. HashSet

    - contains 를 통한 값 유무 확인에서 O(1)이기 때문에 (해시 충돌이 적다고 가정) 이를 기본적으로 사용

    - remove / insert 에서 기본 데이터 적용을 위해 씀

코드

class RandomizedSet {
    private List<Integer> list;
    private Set<Integer> hs;
    private Random random;

    public RandomizedSet() {
        list = new ArrayList<>();
        hs = new HashSet<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(hs.contains(val)) {
            return false;
        }
        list.add(val);
        hs.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(hs.contains(val)) {
            list.remove(Integer.valueOf(val));
            hs.remove(val);
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        int randomIndex = random.nextInt(hs.size());
        return list.get(randomIndex);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */