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

🔈 문제

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.

 

💫 예시

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.

 

🎱 제한

-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

 

 

📚 문제 풀이

문제의 요구 사항을 정리해보자면, 삽입, 삭제 그리고 랜덤한 값 추출하는 동작의 시간복잡도가 모두 O(1) 자료구조를 만드는 것이다. 

 

삽입과 삭제를 O(1)에 처리할 수 있는 자료구조로는 Set이 있다. 하지만 Set에서 랜덤한 값을 추출하는 것은 불가능하다. 인덱스 접근이 안되기 때문이다.

그렇다면 랜덤한 값 추출을 O(1)에 동작하는 자료구조로는 List가 있다. 0부터 현재 자료구조의 길이 중 랜덤한 값을 뽑고 인덱스로 접근하면 되기 때문이다. 그렇지만 리스트에서 삽입은 O(1)이지만 삭제는 O(1)이 아니다. 이유는 삽입 같은 경우에는 가장 뒤에 원소에 값을 추가하여 이전 원소들의 주소의 변함이 없지만 삭제의 경우 삭제하고자 하는 원소를 찾고 그 원소를 삭제하고 삭제된 원소 뒤에 있는 값들은 전부 앞으로 한칸씩 당겨와야 되기 때문이다. 때문에 가장 앞의 원소를 삭제하는데에는 O(n), 가장 뒤의 원소를 삭제하는데에는 O(1)이 소요된다. 

우리는 이점을 이용하면 된다! 

현재 이 문제에서는 순서를 유지할 필요가 없다. 그렇다면 삭제하는 요소를 가장 마지막에 있는 요소랑 위치를 변경하고 마지막으로 이동한 삭제하고자 하는 요소를 삭제한다면, swap O(1), pop O(1) 으로 삭제를 O(1)에 처리할 수 있다.

 

그렇다면 이제 값을 저장할 때 저장하고자 하는 값의 인덱스도 함께 저장해야 한다. 그렇기에 셋대신 Map을 사용하여 키에는 원소를, 값에는 인덱스를 함께 저장할 것이다. 맵 역시 해시 기반으로 동작하기 때문에 삽입 삭제에 O(1)이 소요된다. 

 

 

꽤 야무진 문제였다. 

💻 코드

 

class RandomizedSet {
 
    private Map<Integer, Integer> index;
    private List<Integer> nums;
    private Random rand;
    
    public RandomizedSet() {
        this.index = new HashMap<>();
        this.nums = new ArrayList<>();
        this.rand = new Random();
    }
    
    public boolean insert(int val) {
        if (!index.containsKey(val)) {
            index.put(val, nums.size());
            nums.add(val);
            return true;
        }
        return false;
    }
    
    public boolean remove(int val) {
        if (index.containsKey(val)) {
            int remIdx = index.get(val);
            int lastVal = nums.get(nums.size()-1);
            nums.set(remIdx, lastVal);
            nums.remove(nums.size()-1);
            index.put(lastVal, remIdx);
            index.remove(val);
            
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        int randomIndex = rand.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}
 

 

 

🔗 문제링크 

LeetCode - The World's Leading Online Programming Learning Platform