Intuition 🤔

첫번째로 드는 생각은 일단 한 언어의 많은 API들을 공부해야겠다이다.

1. Random

• java.util.Random
• Random random = new Random()
• random.nextInt(max - min) + min;

2. HashSet

• java.util.HashSet
• HashSet<String> names = new HashSet<>();
• .add, .remove, .contains, .size runs in O(1) time.

3. ArrayList

• java.util.ArrayList
• `ArrayList intList = new ArrayList<>();
• .add(E) O(1), .add(index, e) O(n), .get(index) O(1), .set(index) O(1), .remove(index) O(n), .size() O(1), .isEmpty() O(1), .contains() O(n)

4. HashMap

• java.util.HashMap
• .put(k,v) O(1), .get(key) O(1), .remove() -> removed element O(1), .containsKey() O(1), .containsValue() O(n), .size()

insert와 remove는 그냥 원래 HashSet API대로 사용하면 될 것이다.

getRandom()은 또 다른 배열을 만들어 add()와 remove()를 하는 동안 element들을 하나씩 추가하고 nextInt(size)를 random index로 하여 그 element를 반환하면 될 듯 하다.

-> 하지만 remove() 는 O(n)이어서 이 방법은 안된다.

다른 방법으로 HashMap<Integer, Integer>을 사용해 key에는 RandomSet의 element를 저장하고 value에는 random access에 사용될 ArrayList의 element들의 index를 저장한다. 그리고 swap and pop를 사용해 그 index에 있는 element와 마지막 index에 있는 element와 맞 바꾸고 pop해주면 O(1)이다. 이러면 HashMap에 있는 전에 맨 뒤에 있던 그 element의 index도 바꿔주어야 한다.

이렇게 한다면 .add(), .remove() 도 O(1), getRandom()도 O(1)이다.

First Attempt

import java.util.Random; 
import java.util.HashMap; 

class RandomizedSet {
    private HashMap<Integer, Integer> hm; 
    private ArrayList<Integer> al; 
    private Random random = new Random(); 

    public RandomizedSet() {
        this.hm = new HashMap<>(); 
        this.al = new ArrayList<>(); 
    }
    
    public boolean insert(int val) {
        if (!this.hm.containsKey(val)) {
            this.al.add(val);
            int index = this.al.size(); 
            this.hm.put(val, index);
        }

        return false;
    }
    
    public boolean remove(int val) {
        if (this.hm.containsKey(val)) {
            // first, remove the element in the hashmap and get the index. 
            int index = this.hm.remove(val); 

            // second, swap and pop the element with the last element in the arraylist. 
            int temp = this.al.get(this.al.size() - 1); 
            this.al.set(this.al.size() - 1, val); 
            this.al.set(index, temp);
            this.al.remove(this.al.size() - 1);

            // third, update the index of the swapped element . 
            this.hm.put(temp, index);
            return true; 
        }

        return false;
    }
    
    public int getRandom() {
        int size = this.al.size();
        int randomIndex = random.nextInt(size);
        return this.al.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();
 */

별로 생각을 깊게 안 한 답인 것 같다. remove() 로직이 이상하다.

Second Attempt

import java.util.Random; 
import java.util.HashMap; 

class RandomizedSet {
   private HashMap<Integer, Integer> hm; 
   private ArrayList<Integer> al; 
   private Random random = new Random(); 

   public RandomizedSet() {
       this.hm = new HashMap<>(); // <element, indexInArraylist>
       this.al = new ArrayList<>(); 
   }
   
   public boolean insert(int val) {
       if (!this.hm.containsKey(val)) {
           this.al.add(val);
           this.hm.put(val, this.al.size() - 1);
           return true;
       }

       return false;
   }
   
   public boolean remove(int val) {
       if (this.hm.containsKey(val)) { // if the element exists in the hashset,
           // first, remove the element in the hashmap and get the index. 
           int index = this.hm.remove(val); 

           // second, swap and pop the element with the last element in the arraylist. 
           int toUpdate = this.al.get(this.al.size() - 1);
           // 1. set the index with the last element
           this.al.set(index, toUpdate);

           // 2. update the index of the last element in the hash map

           this.hm.put(toUpdate, index);

           // 3. remove the last element
           this.al.remove(this.al.size() - 1);
           
           return true; 
       }

       return false;
   }
   
   public int getRandom() {
       int size = this.al.size();
       int randomIndex = random.nextInt(size);
       return this.al.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();
*/

거의 다 했다. 하지만 test case 몇개가 통과가 안 됐다.

input:

["RandomizedSet","remove","remove","insert","getRandom","remove","insert"]

[[],[0],[0],[0],[],[0],[0]]

output:

[null,false,false,true,0,true,false]

expected:

[null,false,false,true,0,true,true]

이유를 보니 만약 this.hm.remove(val)를 통해 얻은 this.al에서의 같은 숫자의 인덱스가 ArrayList의 끝에 있다면, 그렇다면 그 숫자에 대한 인덱스 값을 다시 업데이트를 해줄 필요가 없었다는 것이다. 만약 업데이트를 한다면 그 숫자는 다시 HashMap에 들어가게 될 것이다.

Third Attempt

import java.util.Random; 
import java.util.HashMap; 

class RandomizedSet {
    private HashMap<Integer, Integer> hm; 
    private ArrayList<Integer> al; 
    private Random random = new Random(); 

    public RandomizedSet() {
        this.hm = new HashMap<>(); // <element, indexInArraylist>
        this.al = new ArrayList<>(); 
    }
    
    public boolean insert(int val) {
        if (!this.hm.containsKey(val)) {
            this.al.add(val);
            this.hm.put(val, this.al.size() - 1);
            return true;
        }

        return false;
    }
    
    public boolean remove(int val) {
        if (this.hm.containsKey(val)) { // if the element exists in the hashset,
            // first, remove the element in the hashmap and get the index. 
            int index = this.hm.remove(val); 

            // second, swap and pop the element with the last element in the arraylist. 
            int toUpdate = this.al.get(this.al.size() - 1);
            // 1. set the index with the last element
            this.al.set(index, toUpdate);

            // 2. update the index of the last element in the hash map
            if (index != this.al.size() - 1)
                this.hm.put(toUpdate, index);

            // 3. remove the last element
            this.al.remove(this.al.size() - 1);
            
            return true; 
        }

        return false;
    }
    
    public int getRandom() {
        int size = this.al.size();
        int randomIndex = random.nextInt(size);
        return this.al.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();
 */