[LeetCode] 380. Insert Delete GetRandom O(1) - 해시맵(HashMap) + 아이디어(Idea) JAVA

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

코드설명

해시맵(HashMap) + 아이디어(Idea)를 활용합니다.

 

랜덤값을 손쉽게 출력하면서 Average Time Complexity를 O(1)로 하기 위해서는 ArrayList와 HashMap을 함께 활용해주어야 합니다.

먼저, ArrayList를 사용하는 이유는 Random 함수를 O(1)안에 해결하기 위함입니다.

HashMap을 활용하는 이유는, Insert와 Remove, 그리고 특정 val값이 존재하는지 손쉽게 하기 위함입니다.

이떄 HashMap이 결국에는 ArrayList의 Index 위치를 관리하는 역할도 함을 알 수 있습니다.

 

여기서 중요포인트는, remove할때 현재 val의 위치를 lastElement로 덮어씌이게 하면서 val을 삭제시키는 것과 동일한 역할을 하게 합니다.

이유는 HashMap은 ArrayList의 Idx를 관리하는데, 이떄 ArrayList에서 중간값을 삭제하면 한개씩 밀리기에 HashMap에서 처리가 불가능하기 때문입니다.

코드

정답코드1입니다.

class RandomizedSet {
    HashMap<Integer, Integer> valueToArrayIndexHashMap;
    ArrayList<Integer> arr;
    public RandomizedSet() {
        valueToArrayIndexHashMap = new HashMap<>();
        arr = new ArrayList<Integer>();
    }
    
    public boolean insert(int val) {
        if(valueToArrayIndexHashMap.containsKey(val) == true) return false;

        valueToArrayIndexHashMap.put(val, arr.size());
        arr.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(valueToArrayIndexHashMap.containsKey(val) == false) return false;

        int arrIdx = valueToArrayIndexHashMap.get(val);
        int lastElement = arr.get(arr.size() - 1);

        arr.set(arrIdx, lastElement);
        valueToArrayIndexHashMap.put(lastElement, arrIdx);

        arr.remove(arr.size() - 1);
        valueToArrayIndexHashMap.remove(val);

        return true;
    }
    
    public int getRandom() {
        Random random = new Random();
        return arr.get(random.nextInt(arr.size()));
    }
}

/**
 * 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();
 */