380 - Insert Delete GetRandom O(1) (Java)

 

---

 

문제

https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150

 

 

풀이

set 의 형태에서, random 값을 뽑아낼 수 있는 자료구조를 만드는 문제이다.

 

우선 insert 와 remove 를 O(1)에 할려면 set이나 map과 같은 자료구조는 필수적으로 필요하다.

 

그리고  random 값을 O(1)로 뽑아내기 위해서는 리스트나 배열이 필수적이다. 해당 배열의 사이즈를 활용해서 랜덤 인덱스를 뽑고, 그 값에 한 번에 접근할 수 있으니 말이다.

 

난 map 과 배열의 조합으로 문제를 해결했다. 

 

---

우선 배열의 끝을 가리키는 lastIdx 를 선언하고, 이를 -1로 초기화 한다.

 

다음은 map인데 map<값, 배열인덱스> 로 구성할 것이다.

 

insert

 

이렇게 되면 insert 때는 매개변수로 넘어오는 값으로 이미 존재하는지 확인이 가능하고,
존재하지 않는다면 lastIdx 를 증가시킨후에 map 에 추가할 수 있다.

 

map에 값을 추가하였으니 배열에도 lastIdx 에 값을 업데이트 시켜준다.

 

random

 

random 도 단순하게 구현이 가능하다. 배열의 실질적인 끝을 lastIdx 가 가리키고 있으니, 그 사이 인덱스를 랜덤으로 뽑아서 접근한다음 반환해주면 끝이다.

 

remove

 

문제는 remove 이다. 일반적으로 배열에서 값을 하나 삭제한 후에 빈자리를 채우려면 뒤의 값들을 모두 앞으로 끌어와야 하기에 O(n) 의 시간이 소요된다. 

 

때문에 이를 O(1) 로 만드는것이 중요하다.

 

이는 배열에서 삭제하는 값이 있는곳에 가장 뒤의 값을 치환해주는걸로 해결할 수 있다.

 

[3, 1, 2, 4] 라는 배열에서 [1] 을 삭제한다고 하면

 

[3, 4, 2, 4] 로 갱신해주는 것이다.

 

위와 같이 한다음에 단순히 lastIdx 를 하나 줄여주면 문제없이 remove 도 구현할 수 있다!

 

코드

import java.util.*;

class RandomizedSet {

    public Map<Integer, Integer> map;
    public int[] arr = new int[20001];
    public int lastIdx;

    public RandomizedSet() {
        map = new HashMap<>();
        lastIdx = -1;
    }
    // 요소가 없으면 true, 있으면 false
    public boolean insert(int val) {

        // if map has key, return false
        if(map.containsKey(val)){
            return false;
        }

        // if not, add val
        lastIdx++;
        map.put(val, lastIdx);
        arr[lastIdx] = val;

        return true;
    }

    // 요소가 있으면 true, 아니면 false
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }

        map.put(arr[lastIdx], map.get(val)); // 마지막 값의 인덱스를 새롭게 갱신한다.
        arr[map.get(val)] = arr[lastIdx]; // 실제로 위치도 갱신해준다.
        map.remove(val); // 그리고 기존 값은 map 에서 삭제해준다.
        lastIdx--;

        return true;
    }
    
    public int getRandom() {
        return arr[new Random().nextInt(lastIdx+1)];
    }
}