문제링크: 380. Insert Delete GetRandom O(1)

---

📖 문제설명

다음과 같은 기능을 가진 RandomizedSet클래스를 구현하라

• RandomizedSet(): RandomizedSet의 생성자.
• bool insert(int val): val가 없다면 추가를하여 true를 반환, 그렇지 않은 경우 false를 반환
• bool remove(int val): val가 존재한다면 제거후 true를 반환, 그렇지 않다면 false를 반환
• int getRandom(): 현제 가지고 있는 요소중에 랜덤으로 반환. 적어도 하나라도 요소를 가지고 있어야 호출 된다

평균적으로 시간복잡도 O(1)로 작업을 실행한다.

💡 접근방식

시간복잡도 O(1)으로 입력되는 작업들을 수행하는게 핵심이므로 어떤 자료구조를 저장소로 쓸 것이냐에 따라 성능이 달라지는 것을 생각했고 자바컬렉션에 대한 공부로 이어졌다. 일단 입출력이 자주 발생하므로 array와 같은 형식은 성능에 부합하지 않다 생각을 했고 가르키는 주소만 수정하면 되는 LinkedList가 가장 잘 어울리는 저장소라 생각했지만 랜덤으로 요소를 반환하는 작업은 O(1)의 시간 복잡도로 해결 할 수 없었다.

코드:

class RandomizedSet {
    List<Integer> storage;
    Random random;

    public RandomizedSet() {
        storage = new LinkedList<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(storage.contains(val)) return false;
        return storage.add(val);
    }
    
    public boolean remove(int val) {
        return storage.remove(Integer.valueOf(val));
    }
    
    public int getRandom() {
        return storage.get(random.nextInt(storage.size()));
    }
}

📌 개선

하나의 컬랙션만을 사용해서 저장소로 쓰는걸 개선해서 서로의 약점이 되는 성능을 보완할 수 있는 컬랙션을 동시에 사용하면 공간복잡도는 늘어나지만 시간복잡도를 획기적으로 개선할 수 있었다. 위에서는 getRandom()성능이 떨어졌었지만 개선된 코드는 배제했던 array를 사용한 ArrayList로 접근속도를 올리고 Map을 활용하여 입출력을 구현하여 ArrayList를 관리할 수 있게 해주므로 써 모든 작업의 평균 속도를 O(1)로 올릴 수 있었다.

코드:

class RandomizedSet {
    List<Integer> values;
    Map<Integer, Integer> ids; // value - id;
    Random randomizer;

    public RandomizedSet() {
        values = new ArrayList<>();
        ids = new HashMap<>();
        randomizer = new Random();    
    }
    
    public boolean insert(int val) {
        if (ids.containsKey(val)) {
            return false;
        }

        ids.put(val, values.size());
        values.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!ids.containsKey(val)) {
            return false;
        }
        int valId = ids.get(val);
        int lastId = values.size()-1;
        if (valId != lastId) { // doing swap because we have to remove from list with O(1)
            int lastVal = values.get(lastId);
            values.set(valId, lastVal);
            ids.put(lastVal, valId);
        }
        values.remove(lastId);
        ids.remove(val);
        return true;
    }
    
    public int getRandom() {
        return values.get(randomizer.nextInt(values.size()));
    }
}