[LeetCode] 380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

LeetCode

Implement the RandomizedSet class:

- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

RandomizedSet 클래스를 구현하십시오:

- RandomizedSet(): RandomizedSet 객체를 초기화합니다.
- bool insert(int val): 항목 val이 존재하지 않을 경우 집합에 삽입합니다. 항목이 존재하지 않았으면 true를, 존재하면 false를 반환합니다.
- bool remove(int val): 항목 val이 존재할 경우 집합에서 삭제합니다. 항목이 존재했으면 true를, 존재하지 않았으면 false를 반환합니다.
- int getRandom(): 현재 집합의 요소들 중 무작위 요소를 반환합니다 (이 메서드가 호출될 때 최소 하나의 요소가 존재함이 보장됩니다). 각 요소는 반환될 확률이 모두 동일해야 합니다.

각 함수가 평균 O(1)의 시간 복잡도로 동작하도록 클래스의 함수들을 구현해야 합니다.

 

Example

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

---

1. 문제 요구사항 분석

이번 문제는 시간복잡도 O(1)의 Insert, Delete, Random으로 Get 해오는 함수를 구현해야하는 문제

 

2. 접근 전략

😭 처음 생각한 방법: HashSet 사용 => insert와 delete 연산을 O(1)에 처리 / get 연산은 O(N)

HashSet은 내부적으로 데이터의 '인덱스(순서)'를 유지하지 않음.
getRandom을 호출했을 때 무작위 요소를 하나 뽑으려면, Set을 순회하거나 배열로 변환해야 하므로 시간 복잡도가 O(N)이 되어 문제의 O(1) 제약 조건을 만족시킬 수 없음

---

😄 ArrayList와 HashMap 사용: insert할 때 ArrayList와 HashMap에 추가 / delete할 때 배열의 맨 끝 값을 지워야하는 값을 대체 / random에서는 Math.Random() 함수로 인덱스를 구한 후 ArrayList에서 get

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

class RandomizedSet {

    private List<Integer> list;
    private Map<Integer, Integer> map;
    private Random random;

    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random(); // getRandom()을 더 깔끔하게 처리하기 위한 전용 객체
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }

        // 배열의 맨 끝에 들어감
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }

        // 지울 값의 현재 위치(인덱스)와, 배열 맨 끝에 있는 값 가져옴
        int targetIdx = map.get(val);
        int lastVal = list.get(list.size() - 1);

        // 맨 끝 값을 지울 값의 위치로 덮어씌움 (Swap)
        list.set(targetIdx, lastVal);
        
        // 자리가 이동된 맨 끝 값의 새로운 인덱스를 해시맵에 업데이트
        map.put(lastVal, targetIdx);

        // 배열의 맨 끝 공간을 잘라내고, 지우려던 값은 해시맵에서 최종 삭제 (Pop)
        list.remove(list.size() - 1);
        map.remove(val);

        return true;
    }
    
    public int getRandom() {
        // random.nextInt(n)을 사용하면 0부터 n-1까지의 난수를 깔끔하게 뽑아줍니다.
        int randomIdx = random.nextInt(list.size());
        return list.get(randomIdx);
    }
}

 

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

Insert Delete GetRandom O(1) - LeetCode