LeetCode 380 - Insert Delete GetRandom O(1)

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

 

RandomizedSet이라는 class를 작성하는 문제이다.

각 메서드에는 구현해야 할 조건이 있다.

• RandomizedSet() 생성자이다.
• bool insert(int val) set에 val을 삽입하는 메서드이다. 만약 item이 존재하지 않았다면 true, 그렇지 않다면 false를 반환한다.
• bool remove(int val) set에서 val을 제거한다. 만약 item이 존재했었다면 true, 그렇지 않다면 false를 반환한다.
• int getRandom() 현재 set에서 random 원소를 반환한다. 문제 조건상 이 메서드가 호출됐을 때 적어도 하나의 원소가 set에 존재하는 것이 보장된다. 각각의 원소는 동일한 반환 확률을 가지고 있어야 한다.

이러한 메서드들을 평균 O(1)의 시간복잡도로 구현해야 한다.

사실 위의 세 개 메서드는 전혀 문제가 안 된다. Set 인터페이스에 다 구현 돼 있다.

Set 인터페이스의 add와 remove가 정확히 위의 insert, remove 메서드와 동일한 동작을 한다.

핵심은 동일한 확률로 하나를 꺼내 반환하는 getRandom 메서드이다.

하지만 O(1)의 시간복잡도로 꺼내려면 Set을 사용하면 안된다. Set에 있는 데이터를 꺼내려면 순회를 해야 한다.

다시 자료구조부터 살펴보며 선택해 보자.

우선 ArrayList다. 이는 마지막 요소 추가 및 무작위 접근이 O(1)로 가능하지만 특정 값 삭제가 O(N)이다.

HashMap은 삽입, 삭제, 검색이 O(1)로 가능하지만 무작위 요소 선택이 불가능하다.

getRandom은 ArrayList를 사용하면 해결이 가능할 것 같다. 그러면 이제 삽입, 삭제의 문제가 된다.

ArrayList내의 값(val)의 위치를 관리하는 별도 자료구조가 있으면 좋겠다. 그리고 접근이 빨라야 한다. 이게 HashMap이다.

class RandomizedSet {

    private List<Integer> numbers = new ArrayList<>();
    private Map<Integer, Integer> valueMap = new HashMap<>();
    private Random rand;

    public RandomizedSet() {
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if (valueMap.containsKey(val)) {
            return false;
        }

        valueMap.put(val, numbers.size());
        numbers.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!valueMap.containsKey(val)) return false;

        int idxForDelete = valueMap.get(val);
        int lastIdx = numbers.size() - 1;
        int lastValue = numbers.get(lastIdx);
        // 삭제 위치의 값을 마지막 값과 위치 변경        
        numbers.set(idxForDelete, lastValue);
        valueMap.put(lastValue, idxForDelete);

        numbers.remove(lastIdx);
        valueMap.remove(val);
        return true;
    }
    
    public int getRandom() {
        return numbers.get(rand.nextInt(numbers.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();
 */

ArrayList에서 특정 위치의 값을 삭제하는 것은 O(N)의 시간복잡도를 갖는다. 그에 반해 마지막 값의 삭제는 O(1)이다.

따라서 두 값을 교환하면 결과적으로 원하는 위치의 값을 O(1)로 삭제하는 것과 같은 효과를 얻을 수 있다.